• 검색어에 아래의 연산자를 사용하시면 더 정확한 검색결과를 얻을 수 있습니다.
  • 검색연산자
검색연산자 기능 검색시 예
() 우선순위가 가장 높은 연산자 예1) (나노 (기계 | machine))
공백 두 개의 검색어(식)을 모두 포함하고 있는 문서 검색 예1) (나노 기계)
예2) 나노 장영실
| 두 개의 검색어(식) 중 하나 이상 포함하고 있는 문서 검색 예1) (줄기세포 | 면역)
예2) 줄기세포 | 장영실
! NOT 이후에 있는 검색어가 포함된 문서는 제외 예1) (황금 !백금)
예2) !image
* 검색어의 *란에 0개 이상의 임의의 문자가 포함된 문서 검색 예) semi*
"" 따옴표 내의 구문과 완전히 일치하는 문서만 검색 예) "Transform and Quantization"
쳇봇 이모티콘
ScienceON 챗봇입니다.
궁금한 것은 저에게 물어봐주세요.

논문 상세정보


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.

참고문헌 (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 


원문 PDF 다운로드

  • ScienceON :

원문 URL 링크

원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다. (원문복사서비스 안내 바로 가기)

상세조회 0건 원문조회 0건

DOI 인용 스타일