부품외주를 고려한 조립형 Flowshop 일정계획 해법 개선
An Improvement of Algorithms for Assembly-type Flowshop Scheduling Problem with Outsourcing
1
조회
0
다운로드
4
인용
0
참고문헌
키워드
초록
This paper improves algorithms for an assembly-type flowshop scheduling problem in which each job is to assemble two types of components and makespan is the objective measure. For the assembly, one type of the components is outsourced with job-dependent lead time but the other type is fabricated in-house. When both components for a job are prepared, the assembly operation for the job can be started. This problem had been proved to be NP-Complete, so branch-and-bound (B&B) and heuristic algorithms have already been developed. In this paper, we suggest other dominance rules, lowerbound and heutistic algorithms. Also, we develop a new B&B algorithm using these improved bound and dominance rules. The suggested heuristics and B&B algorithm are compared with existing algorithms on randomly-generated test problems.
Abstract
This paper improves algorithms for an assembly-type flowshop scheduling problem in which each job is to assemble two types of components and makespan is the objective measure. For the assembly, one type of the components is outsourced with job-dependent lead time but the other type is fabricated in-house. When both components for a job are prepared, the assembly operation for the job can be started. This problem had been proved to be NP-Complete, so branch-and-bound (B&B) and heuristic algorithms have already been developed. In this paper, we suggest other dominance rules, lowerbound and heutistic algorithms. Also, we develop a new B&B algorithm using these improved bound and dominance rules. The suggested heuristics and B&B algorithm are compared with existing algorithms on randomly-generated test problems.
참고문헌 (13)
- 전재호, "부품외주를 고려한 조립형 Flowshop 일정계획문제 연구", 산업경영시스템학회지, 29(4), pp.34~42 (2006), 한국산업경영시스템학회
- Bertrand, J. W. M., "Production control in engineer-to-order firms", International Journal of Production Economics, 30(31), pp.3~22 (1993)
- Chen, Z. -L., "Supply Chain Scheduling：Conflict and Cooperation in Assembly Systems", Operations Research, 55(6), pp.1072~1089 (2007)
- 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)
- Johnson, S. M., "Optimal two- and three-stage production schedules with setup times included", Naval Research Logistics Quarterly, 1, pp.61~68 (1954)
- Juhn, J., "Analysis of heuristics for a two-stage assembly scheduling problem with component available time constraint" (2006), Submitted to Operations Research Letters for publication
- Koulamas, C., "The three-stage assembly flowshop scheduling problem", Computers & 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)
- 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)
- Tozkapan, A., "A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem", Computers & Operations Research, 30, pp.309~320 (2003)