본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

다 단계 혼합흐름공정 일정계획에서 납기지연 작업 수의 최소화를 위한 대체 목적함수 기반 탐색기법
Surrogate Objective based Search Heuristics to Minimize the Number of Tardy Jobs for Multi-Stage Hybrid Flow Shop Scheduling

최현선    (한국능률협회컨설팅   ); 김형원    (한양대학교 산업공학과   ); 이동호    (한양대학교 산업공학과  );
  • 초록

    This paper considers the hybrid flow shop scheduling problem for the objective of minimizing the number of tardy jobs. In hybrid flow shops, each job is processed through multiple production stages in series, each of which has multiple identical parallel machines. The problem is to determine the allocation of jobs to the parallel machines at each stage as well as the sequence of the jobs assigned to each machine. Due to the complexity of the problem, we suggest search heuristics, tabu search and simulated annealing algorithms with a new method to generate neighborhood solutions. In particular, to evaluate and select neighborhood solutions, three surrogate objectives are additionally suggested because not much difference in the number of tardy jobs can be found among the neighborhoods. To test the performances of the surrogate objective based search heuristics, computational experiments were performed on a number of test instances and the results show that the surrogate objective based search heuristics were better than the original ones. Also, they gave the optimal solutions for most small-size test instances.


  • 주제어

    Hybrid Flow Shops .   Scheduling .   Number of Tardy Jobs .   Search Heuristics .   Surrogate Objectives.  

  • 참고문헌 (28)

    1. Azizoglu, M., Cakmak, E. and Kondakci, S. A. (2001), A flexible flow shop problem with total flow time minimization, European Journal of Operational Research, 132, 528-538 
    2. Chen, B. (1995), Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at on stage, Journal of Operation Research Society, 46, 231-244 
    3. Garey, M. R. and Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company 
    4. Glover, F. (1989), Tabu search: part I, ORSA Journal of Computing, 1, 190-206 
    5. Park, M.-W. and Kim, Y.-D. (1998), A systematic procedure for setting parameters in simulated annealing algorithms, Computers and Operations Research, 25, 207-217 
    6. Choi, H.-S. and Lee, D.-H. (2009), Scheduling algorithms to minimize the number of tardy jobs in two-stage hybrid flow shops, Computers and Industrial Engineering, 56, 113-120 
    7. Lee, C. Y. and Vairaktarakis, G. L. (1994), Minimizing makespan in hybrid flow shops, Operations Research Letters, 16, 149-158 
    8. Lee, G.-C., Kim, Y.-D. and Choi, S.-W. (2004), Bottleneck-focused scheduling for a hybrid flow shop, International Journal of Production Research, 42, 165-181 
    9. Lee, J. S. and Park, S. H. (1999), Scheduling heuristics for a two-stage hybrid flowshop with nonidentical parallel machines, Journal of the Korean Institute of Industrial Engineers, 25, 254-265 
    10. Choi, H.-S. and Lee, D.-H. (2007), A branch and bound algorithm for two-stage hybrid flow shops: minimizing the number of tardy jobs, Journal of the Korean Institute of Industrial Engineers, 33, 213-220 
    11. Choi, H.-S., Kim, H.-W., Lee, D.-H., Yun, J., Yoon, C. Y., and Chae, K. B. (2009), Scheduling algorithms for two-stage reentrant hybrid flow shops: minimizing makespan under the maximum allowable due-dates, International Journal of Advanced Manufacturing Technology, 42, 963-973 
    12. Laguna, M., Barnes, J. W. and Glover, F. (1991), Tabu search methods for a single machine scheduling problem, Journal of Intelligent Manufacturing, 2, 63-74 
    13. Lee, G.-C. and Kim, Y.-D. (2004), A branch-and-bound algorithm for a two-stage hybrid flow shop scheduling problem minimizing total tardiness, International Journal of Production Research, 42, 4731-4743 
    14. Gupta, J. N. D. and Tunc, E. A. (1998), Minimizing tardy jobs in a two-stage hybrid flowshop, International Journal of Production Research, 36, 2397-2417 
    15. Lee, G.-C. (2006), Scheduling methods for a hybrid flowshop with dynamic order arrival, Journal of the Korean Institute of Industrial Engineers, 32, 373-381     
    16. Tsubone, H., Ohba, M., and Uetake, T. (1996), The impact of lot sizing and sequencing on manufacturing performance in a two-stage hybrid flow shop, International Journal of Production Research, 34, 3037-3053 
    17. Kemal, A., Orhan, E. and Alper, D. (2007), Using ant colony optimization to solve hybrid flow shop scheduling problems, International Journal of Advanced Manufacturing Technology, 35, 541-550 
    18. Glover, F., Laguna, M. (1993), Tabu search in Modern Heuristics Techniques for Combinatorial Problems, Blackwell Scientific Publications, Oxford, 70-141 
    19. Kim, S.-I., Choi, H,-S. and Lee, D.-H. (2007), Scheduling algorithms for parallel machines with sequence-dependent setup and distinct ready times: minimizing total tardiness, Proceedings of the Institution of Mechanical Engineers Part B: Journal of Engineering Manufacture, 221, 1087-1096 
    20. Linn, R. and Zhang, W. (1999), Hybrid flow shop scheduling, Computers and Industrial Engineering, 37, 57-61 
    21. Brah, S. A. and Hunsucker J. L. (1991), Branch and bound algorithm for the flow shop with multiple processors, European Journal of Operational Research, 51, 88-99 
    22. Ho, J. C. and Chang, Y. L. (1995), Minimizing the number of tardy jobs for m parallel machines, European Journal of Operational Research, 84, 343-355 
    23. Janiak, A., Kozan, E., Lichtenstein, M. and Oguz, C. (2007), Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion, International Journal of Production Economics, 105, 407-424 
    24. Guinet, A. G. P. and Solomon, M. M. (1996), Scheduling hybrid flow shops to minimize maximum tardiness or maximum completion time, International Journal of Production Research, 34, 1643-1654 
    25. Gupta, J. N. D. (1988), Two-stage hybrid flow shop scheduling problem, Journal of Operation Research Society, 39, 359-364 
    26. Gupta, J. N. D. and Tunc, E. A. (1991), Scheduling for a two-stage hybrid flowshop with parallel machines at the second stage, International Journal of Production Research, 29, 1480-1502 
    27. Mourisli, O. and Pochet, Y. (2000), A branch-and-bound algorithm for the hybrid flow shop, International Journal of Production Research Economics, 64, 113-125 
    28. Fouad, R., Abdelhakim, A. and Salah, E. E. (1998), A hybrid three-stage flowshop problem: efficient heuristics to minimize makespan, European Journal of Operational Research, 109, 321-329 

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기