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

논문 상세정보

작업투입시점과 순서의존적인 준비시간이 존재하는 병렬기계 일정계획을 위한 개선 개미군집 시스템
An Improved Ant Colony System for Parallel-Machine Scheduling Problem with Job Release Times and Sequence-Dependent Setup Times

주철민    (동서대학교 시스템경영공학과  );
  • 초록

    This paper considers a parallel-machine scheduling problem with job release times and sequence-dependent setup times. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines so as to minimize the weighted sum of setup times, delay times, and tardy times. A mathematical model for optimal solution is derived and a meta heuristic algorithm based on the improved ant colony system is proposed in this paper. The performance of the meta heuristic algorithm is evaluated through compare with optimal solutions using randomly generated several examples.


  • 주제어

    Parallel-Machine Scheduling .   Ant Colony System.  

  • 참고문헌 (21)

    1. Dorigo, M., Birattari, M., and Stutzle, T. (2006), Ant Colony Optimization : Artificial Ants as a Computational Intelligence Technique, TR/IRIDIA/2006-023, University Libre De Bruxelles, Belgium 
    2. Dorigo, M. and Blum, C. (2005), Ant colony optimization theory : Asurvey, Theoretical Computer Science, 344, 243-278 
    3. Dorigo, M., Maniezzo, V., and Colorni, A. (1996), The Ant System : Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, 26, 29-41 
    4. Mendes, A. S., Muller, F. M., Franca, P. M., and Moscato, P. (2002), Comparing metaheuristic approaches for parallel machine scheduling problems, Production Planning and Control, 13, 143-154 
    5. Shyu, S. J., Lin, B. M. T., and Lin, P.Y. (2004), Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time, Computers and Industrial Engineering, 47, 181-193 
    6. Ying, K. and Liao, C. (2004), An ant colony system for permutation flow-shop sequencing, Computers and Operations Research, 31, 791-801 
    7. Garey, M. and Johnson, D. (1997), Computers and intractability : A guide to the theory of NP-completeness, New York : W. H. Freeman 
    8. Hahn, C. K., Bragg, D. J., and Shin, D. W. (1989), Impact of the setup variable on capacity and inventory decisions, Academic Management Review, 13, 91-103 
    9. Bell, J. E. and McMullen, P. R. (2004), An colony optimization technique for the vehicle routing problem, Advanced Engineering Informatics, 18, 41-48 
    10. Bobrowski, P. M. and Kim, S. C. (1994), The impact of sequence dependent setup time on job shop scheduling performance, International Journal of Production Research, 32, 1503-1520 
    11. Flynn, B. B. (1987), The effects of setup time on output capacity in cellular manufacturing, International Journal of Production Research, 25, 1761-1772 
    12. Nessah, F., Yalaoui, F., and Chu, C. (2005), New heuristics for identical parallel machine scheduling with Sequence-dependent setup times and dates, In Proceedings of the international conference on industrial engineering and systems management, Marrakech, Morocco, 32- 41 
    13. Dorigo, M. and Di Caro, G. (1999), The Ant Colony Optimization Meta-heuristic, New Ideas in Optimization, McGraw-Hill 
    14. Dorigo, M. and Gambardella, L. M. (1997), Ant Colony System : A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation I, 1, 53-66 
    15. Frederickson, G., Hecht, M. S., and Kim, C. E. (1978), Approximation algorithm for some routing problems, SIAM Journal on Computing, 7, 178-193 
    16. Gharehgozli, A. H., Tavakkoli-Moghaddam, R., and Zaerpour, N. (2009), A fuzzy-mixed-integer goal programming mode for a parallel-machine scheduling problem with sequence- dependent setup times and relaeas dates, Robotics and Computer-Integrated Manufacturing, 25, 853-859 
    17. Pinedo, M. (1995), Scheduling theory, algorithms, and systems, Prentice-Hall 
    18. Tahar, D. N., Yalaoui, F., Chu, C., and Amodeo, L. (2006), A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times, International Journal of Production Economics, 99, 63-73 
    19. Cheng, C. and Mao, C. (2007), A modified ant colony system for solving the traveling salesman problem with time window, Mathematical and Computer Modeling, 46, 1225-1235 
    20. Behnamian, J., Zandieh M., and Ghomi, F. (2009), Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm, Expert Systems with Applications, 36, 9637-9644 
    21. Solimanpur, M., Vart, P., and Shankar, R. (2004), Ant colony optimization algorithm to the inner-cell layout problem in cellular manufacturing, European Journal of Operations Research, 157, 592-606 

 저자의 다른 논문

  • 주철민 (16)

    1. 1999 "로버스트 지수가중 이동평균(EWMA) 관리도" Journal of the Korean Data & Information Science Society = 한국데이터정보과학회지 10 (1): 233~241    
    2. 1999 "사출공장의 생산관리를 위한 정보시스템 구축에 관한 연구" Journal of the Korean Data & Information Science Society = 한국데이터정보과학회지 10 (1): 251~259    
    3. 1999 "섬유산업의 재고관리를 위한 정보시스템 구축에 관한 사례연구" Journal of the Korean Data & Information Science Society = 한국데이터정보과학회지 10 (1): 271~277    
    4. 1999 "고정정반 블록조립 작업장의 일정계획 시스템 개발" 산업공학 = IE Interfaces 12 (4): 586~594    
    5. 2000 "선각 평블록 조립공장 일정계획을 위한 혼합 유전 알고리즘" 經營 科學 = Korean management science review 17 (1): 135~144    
    6. 2000 "다종제품의 동적 로트크기결정 모형에서의 생산준비비용 절감효과에 관한 연구" 산업공학 = IE Interfaces 13 (2): 217~224    
    7. 2002 "다양한 서비스를 제공하는 포털 사이트의 가격·품질 및 서비스 믹스 전략" 대한산업공학회지 = Journal of Korean institute of industrial engineers 28 (3): 291~301    
    8. 2008 "동적 블록수송환경을 위한 트랜스포터 일정계획" 산업공학 = IE Interfaces 21 (3): 274~282    
    9. 2008 "시스템 다이내믹스 모델을 이용한 인터넷 포털 사이트의 네트워크 효과 분석" 한국 시스템 다이내믹스 연구 = Korean system dynamics review 9 (1): 73~92    
    10. 2011 "Single-Machine Total Completion Time Scheduling with Position-Based Deterioration and Multiple Rate-Modifying Activities" Industrial engineering & management systems : an international journal 10 (4): 247~254    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

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

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

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

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

이 논문과 함께 이용한 콘텐츠
이 논문과 함께 출판된 논문 + 더보기