재투입이 존재하는 2단계 흐름공정에서 총 작업 흐름시간을 최소화하는 분지한계방법
Branch and Bound Algorithm for Two-Machine Reentrant Flowshop with the Objective of Minimizing Total Flowtime
2
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
In this paper, we consider a two-machine re-entrant permutation flowshop scheduling problem with the objective of minimizing total flowtime, and suggest branch and bound algorithms for the scheduling problem. In this scheduling problem, each job must be processed twice on each machine, that is, each job should be processed on the two machines in the order of machine 1, machine 2 and then machine 1 and machine 2. In this research, based on the results of existing researches for re-entrant permutation flowshop scheduling problems, various dominance properties, lower bound and heuristic algorithm are suggested for the problem, and those are used to develop branch and bound algorithms. In the computational experiments for evaluation of the performance of the algorithms, the suggested branch and bound algorithms are tested on randomly generated test problems and results are reported.
Abstract
In this paper, we consider a two-machine re-entrant permutation flowshop scheduling problem with the objective of minimizing total flowtime, and suggest branch and bound algorithms for the scheduling problem. In this scheduling problem, each job must be processed twice on each machine, that is, each job should be processed on the two machines in the order of machine 1, machine 2 and then machine 1 and machine 2. In this research, based on the results of existing researches for re-entrant permutation flowshop scheduling problems, various dominance properties, lower bound and heuristic algorithm are suggested for the problem, and those are used to develop branch and bound algorithms. In the computational experiments for evaluation of the performance of the algorithms, the suggested branch and bound algorithms are tested on randomly generated test problems and results are reported.
참고문헌 (13)
- Baker,K.R, "Introduction to Sequencing and Scheduling", pp.148~152 (1974), John Wiley and Sons
- Choi,S.-W, "Minimizing makespan on a two-machine re-entrant flowshop", Journal of the Operational Research Society, 58(7), pp.972~981 (2007)
- Choi,S.-W, "Minimizing makespan on an m-machine re-entrant flowshop", Computers and Operations Research, 35(5), pp.1684~1696 (2008)
- Choi,S.-W, "Minimizing total tardiness on a two", Journal of the Operational Research Society, 199(2), pp.375~384 (2009)
- Della Croce,F, "The two-machine total completion time flow shop problem", European Journal of Operational Research, 90(2), pp.227~237 (1996)
- Demirkol,E, "Decomposition methods for reentrant flow shops with sequence dependent setup times", Journal of Scheduling, 3(3), pp.115~177 (2000)
- Graves,S.C, "Scheduling of re-entrant flow shops", Journal of Operations Management, 3(4), pp.197~207 (1983)
- Hoogeveen,J.A, "Stronger Lagrangean bounds by use of slack variables:Application to machine scheduling problems", Mathematical Programming, 70(1), pp.173~190 (1995)
- Ignall,E, "Application of the branchandbound technique to some flow shop problems", Operations Research, 13(3), pp.400~412 (1965)
- Kim,Y.-D, "A new branch and bound algorithm for minimizing mean tardiness in two-machine flowshops", Computers and Operations Research, 20(4), pp.391~401 (1993)
- Nawaz,M, "A heuristic algorithm for the m-machine,n-job flow-shop scheduling problem", Omega, 11(1), pp.91~95 (1983)
- Pan,J.C.H, "re-entrant permutation flow-shops", Journal of Operational Research Society, 54(6), pp.642~653 (2003)
- van de Velde,S.L, "Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangean relaxation", Annals of Operations Research, 26(1), pp.257~268 (1990)