Abstract

This paper deals with the makespan minimization problem of job shops. The problem is known as one of hard problems to optimize, and therefore, many heuristic methods have been proposed by many researchers. The aim of this study is also to propose a heuristic scheduling method for the problem. However, the difference between the proposed method and many other heuristics is that the proposed method is based on depth-first branch and bound, and thus it is possible to find an optimal solution at least in principle. To accelerate the search, when a node is judged hopeless in the search tree, the proposed flexible branch and bound method can indicate a higher backtracking node. The unexplored nodes are stored and may be explored later to realize the strict optimization. Two methods are proposed to generate the backtracking point based on the critical path of the current best feasible schedule, and the minimum lower bound for the makespan in the unexplored sub-problems. Schedules are generated based on Giffler and Thompson's active schedule generation algorithm. Acceleration of the search by the flexible branch and bound is confirmed by numerical experiment.

주제어

#Scheduling   #Job Shop   #Makespan   #Depth-first Branch and Bound   #Heuristic  

참고문헌 (10)

1. Brinkkotter, W. and Brucker, P. (2001), Solving open benchmark instances for the job-shop problem by parallel head-tail adjustments, Journal of Scheduling, 4, 53-64 
2. Giffler, B. and Thompson, G. L. (1960), Algorithms for solving production-scheduling problems, Operations Research, 8, 487-503 
3. Brucker, P., Jurisch, B., and Sievers, B. (1994), A branch and bound algorithm for the job-shop scheduling problem, Discrete Applied Mathematics, 49, 107-127 
4. Carlier, J. and Pinson, E. (1989), An algorithm for solving the job-shop problem, Management Science, 35, 164-176 
5. Kawata, Y., Morikawa, K., Takahashi, K., and Nakamura, N. (2003), Robustness optimization of the minimum makespan schedules in a job shop, International Journal of Manufacturing Technology and Management, 5, 1-9 
6. Morikawa, K., Takahashi, K., and Tabata, K. (2005), Branch and bound based makespan minimization in job shops guided by search history, Proceedings of the 18th International Conference on Production Research, Salerno, Italy, (in CD-ROM) 
7. Carlier, J. (1982), The one-machine sequencing problem, European Journal of Operational Research, 11, 42-47 
8. Gueret, C., Jussien, N., and Prins, C. (2000), Using intelligent backtracking to improve branch-and-bound methods: An application to open-shop problems, European Journal of Operational Research, 127, 344-354 
9. Pezzella, F. and Merelli, E. (2000), A tabu search method guided by shifting bottleneck for the job shop scheduling problem, European Journal of Operational Research, 120, 297-310 
10. Perregaard, M. and Clausen, J. (1998), Parallel branchand- bound methods for the job-shop scheduling problem, Annals of Operations Research, 83, 137-160 

이 논문을 인용한 문헌 (1)

1. 2010. "" Industrial engineering & management systems : an international journal, 9(2): 178~194  원문보기 상세보기