A Flexible Branch and Bound Method for the Job Shop Scheduling Problem
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.
- 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
- Giffler, B. and Thompson, G. L. (1960), Algorithms for solving production-scheduling problems, Operations Research, 8, 487-503
- 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
- Carlier, J. and Pinson, E. (1989), An algorithm for solving the job-shop problem, Management Science, 35, 164-176
- 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
- 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)
- Carlier, J. (1982), The one-machine sequencing problem, European Journal of Operational Research, 11, 42-47
- 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
- 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
- Perregaard, M. and Clausen, J. (1998), Parallel branchand- bound methods for the job-shop scheduling problem, Annals of Operations Research, 83, 137-160
이 논문을 인용한 문헌 (1)
- 2010. "" Industrial engineering & management systems : an international journal, 9(2): 178~194
유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.
원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.
NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.
- 이 논문과 함께 출판된 논문 + 더보기