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

✍ Scribed by F.J. Hwang; Bertrand M.T. Lin

• Publisher: Elsevier Science
• Year: 2011
• Tongue: English
• Weight: 923 KB
• Volume: 60
• Category: Article
• ISSN: 0360-8352
• DOI: 10.1016/j.cie.2011.01.002

✦ Synopsis

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(n 2 ) 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.