Three-Machine Flowshop Scheduling Problem to Minimize Makespan with Bounded Setup and Processing Times

具設置及加工時間界限之三機台流程式排程問題之最後完工時間最小化

Ali Allahverdi

《工業工程學刊》 25卷1期 (2008/01) Pp. 52-61

https://doi.org/10.29977/JCIIE.200801.0006

摘要

在n個工件的三機台中流程式排程問題中，設置成本被視為與加工時間是分開來的且與加工順序是獨立的，而目標為最小化最後完工時間。在實際發生之前，設置與加工時間二者是未知的變數。然而，設置與加工時間的上限及下限是可預先得知的。針對這一類的問題，針對所有可能的實際設置與加工時間，可能存在著不只一個獨特的最佳解。因此，有必要去儘可能地去獲得一組凌越的排程集合。本論文的目標即是減少凌越集合的大小，而其中一個減少凌越集合的大小的方法就是使用凌越關係。在本論文中，全域及區域的凌越關係被發展出來以解決這個問題。更進一步地，針對一個問題使用所發展的凌越關係來作減少凌越集合的大小的示範，並對一些亂數產生的問題，進行計算上的分析。

關鍵字

排程 ； 流程式 ； 最後完工時間 ； 凌越關係 ； 具界線之設置及加工時間

並列摘要

The problem of scheduling n jobs on a three-machine flowshop is addressed where setup times are considered as separate from processing times and sequence-independent. The objective is to minimize makespan. Both setup and processing times are unknown variables before the actual occurrence of these times. However, a lower bound and an upper bound are given (known) for each setup and processing time. For this problem, there may not exist a unique schedule that remains optimal for all possible realizations of setup and processing times. Hence, it is desirable to obtain a set of dominating set of schedules (which dominate all other schedules) if possible. The objective is to reduce the size of dominating set. One way of reducing the size of dominating set is to come up with dominance relations. In this paper, global and local dominance relations are developed for the problem. Moreover, the use of developed dominance relations to reduce the size of the set is illustrated by an example and computational analysis is conducted on randomly generated problems.

並列關鍵字

Scheduling ； flowshop ； makespan ； dominance relations ； bounded processing and setup times

參考文獻

Allahverdi, A.(2005).Two-machine flowshop scheduling problem to minimize makespan with bounded set-up and processing times.International Journal of Agile Manufacturing.8,145-153.

Allahverdi, A.,C. T. Ng,T. C. E., Cheng,M. Y. Kovalyov(2006).A survey of scheduling problems with setup times or costs.European Journal of Operational Research.

Allahverdi, A.,T. Aldowaisan,Y. No. Sotskov(2003).Two-machine flowshop scheduling problem to minimize makespan or total completion time with random and bounded setup times.International Journal of Mathematics and Mathematical Sciences.39,2475-2486.

Allahverdi, A.,J. N. D. Gupta,T. Aldowiasan(1999).A review of scheduling research involving setup considerations.OMEGA The International Journal of Management Sciences.27,219-239.

Allahverdi, A.,Y. N. Sotskov(2003).Two-machine flowshop minimum length scheduling problem with random and bounded processing times.International Transactions in Operational Research.10,65-76.