Journal
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH
Volume 19, Issue 4, Pages 593-611Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10288-020-00463-w
Keywords
Coupled task scheduling; Single machine; Minimizing makespan; Binary search; Heuristic; Bounds
Categories
Funding
- UTS International Research Scholarship (IRS)
- UTS President's Scholarship (UTSP)
- Australian Research Council - Australian Government [DE170100234]
- Australian Research Council [DE170100234] Funding Source: Australian Research Council
Ask authors/readers for more resources
This paper investigates the coupled task scheduling problem, obtaining competitive lower bounds through procedures like solving 0-1 knapsack problems, proposing a binary search heuristic algorithm, and conducting computational experiments to demonstrate the effectiveness of the method. Results also show the proposed solution method outperforms the standard exact solver Gurobi.
The coupled task scheduling problem aims to schedule a set of jobs, each with at least two tasks and there is an exact delay period between two consecutive tasks, on a set of machines to optimize a performance criterion. We study the problem of scheduling a set of coupled jobs to be processed on a single machine with the objective of minimizing the makespan, which is known to be strongly NP-hard. We obtain competitive lower bounds for the problem through different procedures, including solving 0-1 knapsack problems. We obtain an upper bound by applying a heuristic algorithm. We then propose a binary search heuristic algorithm for the coupled task scheduling problem. We perform extensive computational experiments and show that the proposed method is able to obtain quality solutions. The results also indicate that the proposed solution method outperforms the standard exact solver Gurobi.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available