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

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

10.29977/JCIIE.200801.0006

Ali Allahverdi

排程 ； 流程式 ； 最後完工時間 ； 凌越關係 ； 具界線之設置及加工時間 ； Scheduling ； flowshop ； makespan ； dominance relations ； bounded processing and setup times

工業工程學刊

25卷1期（2008 / 01 / 01）

52 - 61

英文

在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.

1. Chen, S. H.,C. K. Chang,C. L. Kuo(2005).Optimal scheduling in color filter manufacturing.Journal of the Chinese Institute of Industrial Engineers,22,301-308.
   連結：
2. Yang, M. H.,C. C. Lo,H. M. Chen,H. L. Huang(2005).Hybrid genetic algorithms for minimizing the maximum completion time for the wafer probing scheduling problem.Journal of the Chinese Institute of Industrial Engineers,22,218-225.
   連結：
3. 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.
4. 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
5. 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.
6. 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.
7. 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.
8. Chandrasekaran, C.,C. Rajendran,O. V. K. Chetty,D. Hanumanna(2007).Metaheuristics for solving economic lot scheduling problems (ELSP) using time-varying lot-sizes approach.European Journal of Industrial Engineering
9. Johnson, S. M.(1954).Optimal two-and three-stage production schedules with setup times included.Naval Research Logistics Quarterly,1,69-81.
10. Kim, S. C.,P. M. Bobrowski(1997).Scheduling jobs with uncertain setup times and sequence dependency.Omega, International Journal of Management Science,25,437-447.
11. Lai, T. C.,Y. N. Sotskov(1999).Sequencing with uncertain numerical data for makespan minimization.Journal of the Operational Research Society,50,230-243.
12. Lai, T. C.,Y. N. Sotskov,N. Y. Sotskova,F. Werner(1997).Optimal makespan scheduling with given bounds of processing times.Mathematical and Computer Modelling,26,67-86.
13. Li, X.,N. Ye,X. Xu,R. Sawhey(2007).Influencing factors of job waiting time variance on a single machine.European Journal of Industrial Engineering,1,56-73.
14. Logendran, R.,S. Carson,E. Hanson(2005).Group scheduling in flexible flow shops.International Journal of Production Economics,96,143-155.
15. Sotskov, Y. N.,A. Allahverdi,T. C. Lai(2004).Flowshop scheduling problem to minimize total completion time with random and bounded processing times.Journal of Operational Research Society,55,277-286.
16. Tang, L.,L. Huang(2007).Optimal and near-optimal algorithms to rolling batch scheduling for seamless steel tube production.International Journal of Production Economics,105,357-371.