Parallel Machines Scheduling with Sequence-Dependent Setup Times Constraints

被引:4
作者
Hu, Dayong [1 ]
Yao, Zhenqiang [1 ]
机构
[1] Shanghai Jiao Tong Univ, Sch Mech Engn, Shanghai 200240, Peoples R China
关键词
Parallel Machines Scheduling; Sequence-Dependent Setup Times; Lower Bound; Genetic Algorithm;
D O I
10.1166/asl.2011.1551
中图分类号
O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];
学科分类号
07 ; 0710 ; 09 ;
摘要
This paper discusses the parallel machines scheduling problem with the objective of minimizing the maximum completion time. Sequence-dependent setup times are considered. The scheduling problem is formulated as a mixed integer programming model. This is a NP-hard problem, and then a genetic algorithm is developed to obtain near optimal solutions. A lower bound is introduced to evaluate the quality of the solution obtained from the proposed genetic algorithm. Computational experiments are conducted, and the results show that the proposed genetic algorithm can provide reasonable solution within an acceptable computational time.
引用
收藏
页码:2528 / 2531
页数:4
相关论文
共 20 条
  • [1] Allahverdi A., 1999, OMEGA, V27, P2
  • [2] Allahverdi A., 2008, EUR J OPER RES, V187, P3
  • [3] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
  • [4] Dunstall S., 2005, COMPUTERS OPERATIONS, V32, P9
  • [5] Karp R. M, 1972, COMPLEXITY COMPUTER
  • [6] Kim D.-W., 2002, ROBOTICS COMPUTER IN, V18, P3
  • [7] Kurz M. E., 2001, INT J PROD RES, V39, P16
  • [8] Lee S. M., 2004, OMEGA, V32, P2
  • [9] Malmborg C., 1996, EUR J OPER RES, V93, P1
  • [10] Moghaddam R. T., 2009, COMPUTERS OPERATIONS, V36, P2