A binary search algorithm for the general coupled task scheduling problem
- Publisher:
- Springer Science and Business Media LLC
- Publication Type:
- Journal Article
- Citation:
- 4OR, 2020, pp. 1-19
- Issue Date:
- 2020-01-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
© 2020, Springer-Verlag GmbH Germany, part of Springer Nature. 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.
Please use this identifier to cite or link to this item: