부품 생산과 조립으로 구성된 2단계 조립 일정계획의 Flowtime 최소화 연구
Heuristic Algorithms for Minimizing Flowtime in the 2-Stage Assembly Flowshop Scheduling
1
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
This paper considers a 2-stage assembly flowshop scheduling problem where each job is completed by assembling multiple components. The problem has the objective measure of minimizing total completion time. The problem is shown to be NP-complete in the strong sense. Thus, we derive some solution properties and propose three heuristic algorithms. Also, a mixed-integer programming model is developed and used to generate a lower bound for evaluating the performance of proposed heuristics. Numerical experiments demonstrate that the proposed heuristics are superior over those of previous research.
Abstract
This paper considers a 2-stage assembly flowshop scheduling problem where each job is completed by assembling multiple components. The problem has the objective measure of minimizing total completion time. The problem is shown to be NP-complete in the strong sense. Thus, we derive some solution properties and propose three heuristic algorithms. Also, a mixed-integer programming model is developed and used to generate a lower bound for evaluating the performance of proposed heuristics. Numerical experiments demonstrate that the proposed heuristics are superior over those of previous research.
참고문헌 (17)
- 전재호, "부품외주를 고려한 조립형 Flowshop 일정계획문제 연구", 산업경영시스템학회지, 29(4), pp.34~42 (2006), 한국산업경영시스템학회
- 윤상흠, "부품외주를 고려한 조립형 Flowshop 일정계획 해법 개선", 산업경영시스템학회지, 31(2), pp.80~93 (2008), 한국산업경영시스템학회
- Baker, K. R, "Introduction to Sequencing and Scheduling" (1974), John Wiley and Sons
- Du,J, "Minimizing mean flow time in two-machine open shops and flow shops", Journal of Algorithms, 14(1), pp.24~44 (1993)
- Garey,M.R, "Computers and Intractability-A Guide to the Theory of NP-Completeness" (1979), Freeman
- Graham,R.L, "Optimization and approximation in deterministic sequencing and scheduling:A survey", Annals of Discrete Mathematics, 5, pp.287~326 (1979)
- Hariri,A.M.A, "A branch and bound algorithm for the two-stage assembly scheduling problem", European Journal of Operational Research, 103, pp.547~556 (1997)
- Koulamas,C, "The three-stage assembly flowshop scheduling problem", Computers and Operations Research, 28, pp.689~704 (2001)
- Kovalyov,M.Y, "Batching decisions for assembly production systems", European Journal of Operational Research, 157, pp.620~642 (2004)
- Lee,C.Y, "Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem", Management Science, 39, pp.616~625 (1993)
- Lin,B.M.T, "Scheduling in an assembly-type production chain with batch transfer", OMEGA:The International Journal of Management Science, 35(2), pp.143~151 (2007)
- Pinedo,M, "Scheduling Theory, Algorithms, and Systems" (2002), Prentice-Hall
- Potts,C.N, "The two-stage assembly scheduling problem:Complexity and approximation", Operations Research, 43, pp.346~355 (1995)
- Sun,X, "Powerful heuristics to minimize makespan in fixed,3-machine,assembly-type flowshop scheduling", European Journal of Operational Research, 146, pp.498~516 (2003)
- Sung,C.S, "Makespan minimization for a 2-stage assembly scheduling subject to component available time constraint", International Journal of Production Economics, 119, pp.392~401 (2009)
- Taha,A.H, "Operations Research-An Introduction" (1997), Prentice Hall
- Tozkapan,A, "A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem", Computers and Operations Research, 30, pp.309~320 (2003)