標題: Coupled-task scheduling on a single machine subject to a fixed-job-sequence
作者: Hwang, F. J.
Lin, Bertrand M. T.
資訊管理與財務金融系 註:原資管所+財金所
Department of Information Management and Finance
關鍵字: Coupled tasks;Exact delays;Fixed-job-sequence;Makespan
公開日期: 1-May-2011
摘要: 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. (C) 2011 Elsevier Ltd. All rights reserved.
URI: http://dx.doi.org/10.1016/j.cie.2011.01.002
http://hdl.handle.net/11536/8963
ISSN: 0360-8352
DOI: 10.1016/j.cie.2011.01.002
期刊: COMPUTERS & INDUSTRIAL ENGINEERING
Volume: 60
Issue: 4
起始頁: 690
結束頁: 698
Appears in Collections:Articles


Files in This Item:

  1. 000289395500023.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.