Method for multi-stage alternative grouping parallel machines scheduling problem
MIAO Feng1, XIE An-huan1, WANG Fu-an2, YU Feng2, ZHOU Hua1
1. State Key Laboratory of Fluid Power Transmission and Control, Zhejiang University, Hangzhou 310027, China; 2.Jiujiang Branch of 707 Research Institute of CSIC, Jiujiang 332007, China
To solve the mixed flow scheduling problem with multi-stage alternative grouping parallel machines, the mathematical model to minimize the maximum completion time was constructed and a hybrid heuristic-genetic algorithm was developed, the algorithm bases on piecewise independent coding method and modified genetic operators. The optimal decision variables of scheduling rules is determined by the global search ability of genetic algorithm. Scheduling scheme of each stage is determined by using the decision variables and the hybrid heuristic rules which contains a variety of scheduling rules. The algorithm can solve path selection sub-problems and processing sorting sub-problems at the same time, and the results automatically satisfy model constraints. This algorithm has following advantages: high arithmetic speed, optimum results taking into higher rates of load-balancing and etc. Simulation examples of different scales verify the effectiveness of the algorithm. The comparison indicates that the composite indicator of this algorithm is superior to that of single heuristic-genetic algorithms．
［1］ 刘志雄, 王少梅. 基于粒子群算法的并行多机调度问题研究［J］. 计算机集成制造系统, 2006, 12(2): 183-187．
LIU Zhi-xiong, WANG Shao-mei. Research on parallel machines scheduling problem based on particle swarm optimization algorithm ［J］. Computer Integrated Manufacturing Systems, 2006, 12(2): 183-187．
［2］ 贺仁杰, 谭跃进. 具有时间窗口约束的并行机床调度问题研究［J］. 系统工程, 2004, 22(5): 18-22．
HE Ren-jie, TAN Yue-jin. On parallel machine scheduling problem with time windows ［J］. Systems Engineering, 2004, 22(5): 18-22．
［3］ 胡大勇, 姚振强. 调整时间与顺序相关的等同并行机调度［J］. 机械工程学报, 2011, 47(16): 160-165．
HU Da-yong, YAO Zhen-qiang. Identical parallel machines scheduling with sequence-dependent setup times ［J］. Journal of Mechanical Engineering, 2011, 47(16): 160-165．
［4］ GUPTA J N D. Two-stage hybrid flow shop scheduling problem ［J］. Journal of the Operational Research Society, 1988, 39(4): 359-364．
［5］ OGUZ C, LIN B M T, EDWIN C T C. Two-stage flow shop scheduling with a common second-stage machine ［J］. Computers & operations research, 1997, 24(12): 1169-1174．
［6］ HARIRI A M A, POTTS C N. A branch and bound algorithm for the two-stage assembly scheduling problem ［J］. European Journal of Operational Research, 1997, 103(3): 547556．
［7］ 赵月, 胡玉梅. 求解可重入并行机调度的混台禁忌搜索算法［J］.计算机应用, 2012, 32(9): 2451-2454．
ZHAO Yue, HU Yu-mei. Hybrid tabu search for scheduling reentrant jobs on parallel machines ［J］. Journal of Computer Applications, 2012, 32(9): 2451-2454．
［8］ 张洁, 张朋, 刘国宝. 基于两阶段蚁群算法的带非等效并行机的作业车间调度［J］. 机械工程学报, 2013, 49(6): 136-144．
ZHANG Jie, ZHANG Peng, LIU Guo-bao. Two-stage ant colony algorithm based job shop scheduling with unrelated parallel machines ［J］. Journal of Mechanical Engineering, 2013, 49(6): 136-144．
［9］ 陈亮, 王世进, 周炳海. 柔性作业车间调度问题的集成启发式算法［J］. 计算机工程, 2008, 34(1): 256-258．
CHEN Liang, WANG Shi-jin, ZHOU Bing-hai. Integrated heuristic algorithm for flexible job-shop scheduling problems ［J］. Computer Engineering, 2008, 34(1): 256-258．
［10］ 庄新村, 卢宇灏, 李从心. 基于遗传算法的车间调度问题［J］. 计算机工程, 2006, 32(1): 193-194．
ZHUANG Xin-cun, LU Yu-hao, LI Cong-xin. Solving job shop scheduling problem by genetic algorithm ［J］. Computer Engineering, 2006, 32(1): 193-194．
［11］ ZHENG D Z, WANG L. An effective hybrid heuristic for flow shop scheduling ［J］. The International Journal of Advanced Manufacturing Technology, 2003, 21(1): 38-44．
