[논문]A Flexible Branch and Bound Method for the Job Shop Scheduling Problem

Morikawa, Katsumi; Takahashi, Katsuhiko

A Flexible Branch and Bound Method for the Job Shop Scheduling Problem 원문보기

Industrial engineering & management systems : an international journal, v.8 no.4, 2009년, pp.239 - 246

Morikawa, Katsumi (Department of Artificial Complex Systems Engineering, Graduate School of Engineering, Hiroshima University) , Takahashi, Katsuhiko (Department of Artificial Complex Systems Engineering, Graduate School of Engineering, Hiroshima University)

Abstract ▼ AI-Helper

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.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

가설 설정

2) The operation time is deterministic and sequence-independent. All jobs arrive at the shop at time zero and their moving times between machines are negligible.

제안 방법

In this experiment, we focus on Method CP& LB and Method LB, both decide the backtracking node, and parameter values were fixed based on preliminary experiments.
However, the optimality of these solutions could not be proved in five minutes. Therefore an additional lengthy experiment was implemented to further investigate the proposed flexible branch and bound method as a strict optimization method by solving eight problems with 10 jobs and 10 machines. Based on the discussion described above, the backtracking node is firstly decided based on the critical path of the current best feasible schedule, and the size of the space for storing sub-problem lists was set to 10,000 in order to avoid the additional computational burden caused by list exchange operations.
This paper proposes another approach to the acceleration of the depth-first branch and bound method, especially in finding good solutions in an earlier stage of the search. To realize this goal we introduce a flexible control method within the search engine.

이론/모형

Giffler and Thompson’s active schedule generation algorithm (Giffler and Thompson, 1960) is adopted as a basic algorithm of makespan minimization in this study.
The focused problem is the makespan minimization of job shops based on Giffler and Thompson’s active schedule generation algorithm.
This study therefore attempts to find a minimum makespan schedule based on Giffler and Thompson’s active schedule generation algorithm.

성능/효과

The length of the array for storing subproblem lists was 10, and the threshold value to interrupt the current search was 100,000. All computations were terminated after five minutes of searches if the flexible branch and bound method could not find an optimal solution with the confirmation of its optimality.

참고문헌 (10)

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

상세보기
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. (1982), The one-machine sequencing problem, European Journal of Operational Research, 11, 42-47

상세보기
Carlier, J. and Pinson, E. (1989), An algorithm for solving the job-shop problem, Management Science, 35, 164-176

상세보기
Giffler, B. and Thompson, G. L. (1960), Algorithms for solving production-scheduling problems, Operations Research, 8, 487-503

상세보기
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

상세보기
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)
Perregaard, M. and Clausen, J. (1998), Parallel branchand- bound methods for the job-shop scheduling problem, Annals of Operations Research, 83, 137-160
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

상세보기

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

A Flexible Branch and Bound Method for the Job Shop Scheduling Problem 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

가설 설정

제안 방법

이론/모형

성능/효과

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

A Flexible Branch and Bound Method for the Job Shop Scheduling Problem 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

가설 설정

제안 방법

이론/모형

성능/효과

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

Morikawa, Katsumi (4) Takahashi, Katsuhiko (5)

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

AI 본문요약
AI-Helper