Bicriteria scheduling in a two-machine permutation flowshop

檔案

日期

2006-06-15

類型

期刊名稱

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH

卷期與頁次

第 44 卷第 12 期,頁 2299–2312

ISSN

0020-7543

語言

英文

摘要

In this paper we consider a production scheduling problem in a two-machine flowshop. The bicriteria objective is a linear combination or weighted sum of the makespan and total completion time. This problem is computationally hard because the special case concerning the minimization of the total completion time is already known to be strongly NP-hard. To find an optimal schedule, we deploy the Johnson algorithm and a lower bound scheme that was previously developed for total completion time scheduling. Computational experiments are presented to study the relative performance of different lower bounds. While the best known bound for the bicriteria problem can successfully solve test cases of 10 jobs within a time limit of 30 min, under the same setting our branch-and-bound algorithm solely equipped with the new scheme can produce optimal schedules for most instances with 30 or less jobs. The results demonstrate the convincing capability of the lower bound scheme in curtailing unnecessary branching during problem-solving sessions. The computational experience also suggests the practical significance and potential implications of this scheme.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Lin, B., & Wu, J. (2006). Bicriteria scheduling in a two-machine permutation flowshop. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 44(12), 2299–2312. https://doi.org/10.1080/00207540500446394

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/12143