Method for multi-stage alternative grouping parallel machines scheduling problem

doi:10.3785/j.issn.1008-973X.2015.05.008

JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE)

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

Download:

PDF(811KB) HTML
Export: BibTeX | EndNote (RIS)

Abstract

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．

Published: 26 December 2015

CLC:	TP 18
	TP 301.6

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors

Cite this article:

MIAO Feng, XIE An-huan, WANG Fu-an, YU Feng, ZHOU Hua. Method for multi-stage alternative grouping parallel machines scheduling problem. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(5): 866-872.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2015.05.008 OR http://www.zjujournals.com/eng/Y2015/V49/I5/866

多阶段可替换分组并行机调度问题的求解

针对一类多阶段可替换分组并行机混流生产调度问题,以最小化最大完工时间为目标建立问题的数学模型,提出一种嵌入混合启发规则的遗传算法,采用分段独立编码的染色体和改进的遗传算子.依靠遗传算法的全局搜索能力确定启发规则的最优决策变量,根据决策变量采用包含多种规则的混合规则确定各阶段调度方案；同时解决了调度问题的路径选择子问题和加工排序子问题,调度方案自动满足模型约束.算法求解速度快,求解结果具有较高的负荷平衡率.针对不同规模的算例,仿真验证了算法的有效性,仿真结果表明该算法的综合性能指标优于嵌入单一启发规则的遗传算法.

［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．

[1]	ZHU Dong-yang, SHEN Jing-yi, HUANG Wei-ping, LIANG Jun. Fault classification based on modified active learning and weighted SVM[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(4): 697-705.

[2]	FENG Xiao yue, LIANG Yan chun, LIN Xi xun, GUAN Ren chu. Research and development of never-ending language learning[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(1): 82-88.

[3]	QIU Ri hui, LIU Kang ling, TAN Hai long, LIANG Jun. Classification algorithm based on extreme learning machine and its application in fault identification of Tennessee Eastman process[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(10): 1965-1972.

[4]	JI Yu,QIU Qing ying,FENG Pei en,HUANG Hao. Extraction and utilization of design knowledge in international patent classification[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(3): 412-418.

[5]	JU Bin, QIAN Yun-tao, YE Min-chao. Collaborative filtering algorithm based on structured projective nonnegative matrix factorization[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(7): 1319-1325.

[6]	WANG Guo-fang, FANG Zhou, LI Ping. Natural Actor-Critic based on batch recursive least-squares[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(7): 1335-1342.

[7]	TAN Hailong, LIU Kangling, JIN Xin, SHI Xiang rong, LIANG Jun. Multivariate time series classification based on μσ-DWC feature and tree-structured M-SVM[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(6): 1061-1069.

[8]	WANG Li-jun, HUANG Zhong-chao, ZHAO Yu-qian. New spatial-coherent latent topic model based on super-pixel segmentation and scene classification method[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(3): 402-408.

[9]	WANG Cheng-long, LI Cheng, FENG Yi-ping, RONG Gang. Dispatching rule extraction method for job shop scheduling problem[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(3): 421-429.

[10]	YU Jun, WANG Zeng-fu. Video stabilization based on empirical mode decomposition and several evaluation criterions[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2014, 48(3): 423-429.

[11]	LIU Ye-feng, XU Guan-qun, PAN Quan-ke, CHAI Tian-you. Magnetic material molding sintering production scheduling optimization method and its application[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2013, 47(9): 1517-1523.

[12]	LIN Yi-ning, WEI Wei, DAI Yuan-ming. Semi-supervised Hough Forest tracking method[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2013, 47(6): 977-983.

[13]	HAO Chuan-chuan, FANG Zhou, LI Ping. Output feedback reinforcement learning control method based on reference model[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2013, 47(3): 409-414.

[14]	WANG Peng-jun, WANG Zhen-hai, CHEN Yao-wu, LI Hui. Searching the best polarity for fixed polarity Reed-Muller circuits based on delay model[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2013, 47(2): 361-366.

[15]	LI Kan, HUANG Wen-xiong, HUANG Zhong-hua. Multi-sensor detected object classification method based on support vector machine[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2013, 47(1): 15-22.

Viewed

Full text

Abstract

Cited

Shared

Discussed