지연 스케쥴을 허용하는 납기최소화 잡샵 스케쥴링 알고리즘
Dispatching Rule based Job-Shop Scheduling Algorithm with Delay Schedule for Minimizing Total Tardiness
2
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
This study focuses on a job-shop scheduling problem with the objective of minimizing total tardiness for the job orders that have different due dates and different process flows. We suggest the dispatching rule based scheduling algorithm to generate fast and efficient schedule. First, we show the delay schedule can be optimal for total tardiness measure in some cases. Based on this observation, we expand search space for selecting the job operation to explore the delay schedules. That means, not only all job operations waiting for process but also job operations not arrived at the machine yet are considered to be scheduled when a machine is available and it is need decision for the next operation to be processed. Assuming each job operation is assigned to the available machine, the expected total tardiness is estimated, and the job operation with the minimum expected total tardiness is selected to be processed in the machine. If this job is being processed in the other machine, then machine should wait until the job arrives at the machine. Simulation experiments are carried out to test the suggested algorithm and compare with the results of other well-known dispatching rules such as EDD, ATC and COVERT, etc. Results show that the proposed algorithm, MET, works better in terms of total tardiness of orders than existing rules without increasing the number of tardy jobs.
Abstract
This study focuses on a job-shop scheduling problem with the objective of minimizing total tardiness for the job orders that have different due dates and different process flows. We suggest the dispatching rule based scheduling algorithm to generate fast and efficient schedule. First, we show the delay schedule can be optimal for total tardiness measure in some cases. Based on this observation, we expand search space for selecting the job operation to explore the delay schedules. That means, not only all job operations waiting for process but also job operations not arrived at the machine yet are considered to be scheduled when a machine is available and it is need decision for the next operation to be processed. Assuming each job operation is assigned to the available machine, the expected total tardiness is estimated, and the job operation with the minimum expected total tardiness is selected to be processed in the machine. If this job is being processed in the other machine, then machine should wait until the job arrives at the machine. Simulation experiments are carried out to test the suggested algorithm and compare with the results of other well-known dispatching rules such as EDD, ATC and COVERT, etc. Results show that the proposed algorithm, MET, works better in terms of total tardiness of orders than existing rules without increasing the number of tardy jobs.
참고문헌 (17)
- Armentano, V. A., "Tabu search for minimizing total tardiness in a job shop", International Journal of Production Economics, 63(2), pp.131~140 (2000)
- 방준영, "Two-Level Hierarchical Production Planning for a Semiconductor Probing Facility", 한국산업경영시스템학회지, 38(4), pp.159~167 (2015), 한국산업경영시스템학회
- Braune, R., "Enhancing local search algorithms for solving job shops with minsum objectives by approximate move evaluation", Journal of Scheduling, 16(5), pp.495~518 (2013)
- Bulbul, K., "A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem", Computers and operations Research, 38(6), pp.967~983 (2011)
- Chaudhry, I. A., "A research survey : review of flexible job shop scheduling techniques", International Transactions in Operational Research, 23(3), pp.551~591 (2016)
- de Bontridder, K. M. J., "Minimizing total weighted tardiness in a generalized job shop", Journal of Scheduling, 8(6), pp.479~496 (2005)
- Essafi, I., "A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem", Computers and Operations Research, 35(8), pp.2599~2616 (2008)
- Jayamohan, M. S., "New dispatching rules for job shop scheduling : A step forward", International Journal of Production Research, 38(3), pp.563~586 (2000)
- Mattfeld, D. C., "An efficient genetic algorithm for job shop scheduling with tardiness objectives", European Journal of Operational Research, 155(3), pp.616~630 (2004)
- 박경민, "복잡한 생산라인에서 효율적 공정관리 기법 도입에 따른 공정흐름 및 생산성 개선 연구", 한국산학기술학회논문지, 17(5), pp.305~315 (2016), 한국산학기술학회[DOI]
- Pinedo, M. L., "A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop", Naval Research Logistics, 46(1), pp.1~17 (1999)
- Singer, M., "Computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops", IIE Transactions, 30, pp.109~119 (1998)
- Vepsalainen, A. P. J., "Priority rules for job shops with weighted tardiness costs", Management Science, 33(8), pp.1035~1047 (1987)
- Zhang, R., "A neighbourhood property for the ob shop scheduling problem with application to hybrid particle swarm optimization", IMA Journal of Management Mathematics, 24(1), pp.111~134 (2013)
- Zhang, R., "A PMBGA to optimize the selection of rules for job shop scheduling based on the Giffler-Thompson algorithm", Journal of Applied Mathematics, 2012, pp.1~17 (2012)
- Zhang, R., "A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective", Computers and Operations Research, 38(5), pp.854~867 (2011)
- Zhang, R., "A hybrid artificial bee colony algorithm for the job shop scheduling problem", International Journal of Production Economics, 141(1), pp.167~178 (2013)