Coupled-task scheduling on a single machine subject to a fixed job sequence

Publication Type:
Journal Article
Citation:
Computers and Industrial Engineering, 2011, 60 (4), pp. 690 - 698
Issue Date:
2011-01
Full metadata record
Files in This Item:
Filename Description Size
2012001329OK.pdfPublished Version922.91 kB
Adobe PDF
This paper investigates single-machine coupled-task scheduling where each job has two tasks separated by an exact delay. The objective of this study is to schedule the tasks to minimize the makespan subject to a given job sequence. We introduce several intriguing properties of the fixed-job-sequence problem under study. While the complexity status of the studied problem remains open, an O(n2) algorithm is proposed to construct a feasible schedule attaining the minimum makespan for a given permutation of 2n tasks abiding by the fixed-job-sequence constraint. We investigate several polynomially solvable cases of the fixed-job-sequence problem and present a complexity graph of the problem.
Please use this identifier to cite or link to this item: