Hybrid Genetic Algorithm for Distributed Flow Shop Inverse Scheduling Problem

doi:10.3901/JME.2022.06.295

Abstract

Abstract: Distributed scheduling is a new mode of intelligent manufacturing, which is in urgent need of new scheduling methods to meet the Dynamic and changeable market demand. To solve the distributed permutation flow shop problem, the inverse scheduling method is used to optimize the job shop scheduling by minimizing the processing parameters. Aiming at minimizing the adjusted processing time, a mathematical model of flow shop reverse scheduling is established, and a hybrid genetic optimization Algorithm is proposed under the framework of genetic algorithm. Firstly, based on the characteristics of the inverse scheduling parameters, an improved operation-based decimal mechanism double coding scheme is proposed, which can adjust the parameters and ensure the possible solution. Secondly, a hybrid initialization method is adopted by improving the NEH heuristic method and the rule-based method, in order to coordinate the ability of global search and local search, the local search strategy and the double-population cooperative search strategy with learning mechanism are designed. In order to verify the performance of the proposed algorithm, three algorithms are compared and analyzed based on the problem examples. The results show that the proposed algorithm can solve the distributed pipeline inverse scheduling problem more effectively.

Key words: distributed scheduling, inverse scheduling, flow shop scheduling, hybrid genetic algorithm, population coordination

CLC Number:

TP319

MU Jianhui, Duan Peiyong, GAO Liang, Peng Wuliang, Cong Jianchen. Hybrid Genetic Algorithm for Distributed Flow Shop Inverse Scheduling Problem[J]. Journal of Mechanical Engineering, 2022, 58(6): 295-308.

References

[1] 吴秀丽，刘夏晶. 差分进化算法求解分布式柔性作业车间调度问题[J]. 计算机集成制造系统，2019，25(10)：2539-2558. WU Xiuli，LIU Xiajing. Differential evolution algorithm for solving distributed flexible job shop scheduling problem[J]. Computer Integrated Manufacturing Systems，2019，25(10)：2539-2558.
[2] 钱斌，王凌，黄德先, 等. 动态零等待流水线调度问题的滚动策略及优化算法[J]. 控制与决策，2009，24(4)：481-487. QIAN Bin，WANG Ling，HUANG Dexian，et al. Rolling strategy and optimization algorithm for dynamic no-wait flow shop scheduling problem[J]. Control and Decision，2009，24(4)：481-487.
[3] SAUER J，SUELMANN G，APPELRATH H J. Multi-site scheduling with fuzzy concepts [J]. International Journal of Approximate Reasoning，1998,19(1/2)：145-160.
[4] ZHANG Hao，ZHAO Fu，SUTHERLAND J W. Energy-efficient scheduling of multiple manufacturing factories under real-time electricity pricing[J]. CIRP Annals-Manufacturing Technology，2015，64(1)：41‐44.
[5] RIBAS I，COMPANYS R，TORT-MARTORELL X. Efficient heuristics for the parallel blocking flow shop scheduling problem[J]. Expert Systems with Applications，2017，74：41‐54.
[6] BEHNAMIAN J.Matheuristic for the decentralized factories scheduling problem[J]. Applied Mathematical Modelling，2017，47：668‐684.
[7] NADERI B,RUIZ R. A scatter search algorithm for the distributed permutation flowshop scheduling problem[J]. European Journal of Operational Research，2014，239(2)：323‐334
[8] FRAMINAN J M.A bounded search iterated greedy algorithm for the distributed permutation flowshop scheduling problem[J]. International Journal of Production Research，2015，53(4)：1111‐1123.
[9] GAO J，CHEN R，DENG W，et al. An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem[J]. International Journal of Production Research，2013，51(3)：641‐651.
[10] BEHNAMIAN J，GHOMI S M T F. Minimizing cost-related objective in synchronous scheduling of parallel factories in the virtual production network[J]. Applied Soft Computing，2015，29，221‐232.
[11] WANG S Y，WANG L，LIU M，et al. An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem[J]. International Journal of Production Economics，2013，145(1)：387‐396.
[12] 沈婧楠，王凌，王圣尧. 求解分布式置换流水线调度问题的化学反应优化算法[J]. 清华大学学报，2015，55(11)：1184‐1189. SHEN Jingnan，WANG Ling，WANG Shengyao. Chemical reaction optimization algorithm for the distributed permutation flowshop scheduling problem[J]. Journal of Tsinghua University，2015，55(11)：1184‐1189.
[13] KOMAKI M，MAL AKOOTI B. General variable neighborhood search algorithm to minimize makespan of the distributed no-wait flow shop scheduling problem[J]. Production Engineering，2017，11(3)：315‐329.
[14] WANG K，HUANG Y，QIN H. A fuzzy logic-based hybrid estimation of distribution algorithm for distributed permutation flowshop scheduling problems under machine breakdown[J]. Journal of the Operational Research Society，2016，67(1)：68‐82.
[15] CHEN Jingfang，WANG Ling，PENG Zhiping. A collaborative optimization algorithm for energy-efficient multi-objective distributed no-idle flow-shop scheduling[J]. Swarm and Evolutionary Computation 2019，50 (4)：100557.
[16] DENG Jin，WANG Ling，WANG Shengyao，et al. A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem[J]. International Journal of Production Research，2016，54 (12)：3561-3577.
[17] XIONG F L，XING K Y，WANG F，et al. Minimizing the total completion time in a distributed two stage assembly system with setup times[J]. Computers & Operations Research，2014，47(1)：92-105.
[18] FU Yaping，TIAN Guangdong，FATHOLLAHI-FARD A M，et.al. Stochastic multi-objective modelling and optimization of an energy-conscious distributed permutation flow shop scheduling problem with the total tardiness constraint[J]. Journal of Cleaner Production，2019，226(20)：515-525.
[19] RIFAI A P，NGUYEN H T，DAWAL S Z M. Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling[J]. Applied Soft Computing，2016，40：42-57.
[20] 高珊. 基于离散人工蜂群算法的零空闲/分布式置换流水车间调度方法研究[D]. 武汉：华中科技大学，2018. GAO Shan. A discrete artificial bee colony algorithm for the no-idle/distributed permutation flowshop scheduling[D]. Wuhan：Huazhong University of Science and Technology，2018.
[21] LU Chao，GAO Liang，LI Xinyu，et al. A multi-objective approach to welding shop scheduling for makespan，noise pollution and energy consumption[J]. Journal of Cleaner Production. 2018，196：773-787.
[22] WANG B，WANG X，LAN F，et al. A hybrid local-search algorithm for robust job-shop scheduling under scenarios[J]. Applied Soft Computing，2018，62：259-271.
[23] 刘长平，叶春明. 求解零空闲置换流水车间调度问题的离散萤火虫算法[J]. 系统管理学报，2014，5(5)：723-727. LIU Changping，YE Chunming. A discrete firefly algorithm for minimizing the makespan in the no-idle permutation flow shops[J]. Journal of Systems & Management，2014，5(5)：723-727.
[24] 潘全科，赵保华，屈玉贵，等. 一类解决无等待流水车间调度问题的蚁群算法[J]. 计算机集成制造系统，2007，13(9)：1801-1804. PAN Quanke，ZHAO Baohua，QU Yugui，et al. Ant-colony heuristic algorithm for no-wait flow shop problem with makespan criterion[J]. Computer Integrated manufacturing Systems，2007，13(9)：1801-1804.
[25] NADERI B，RUIZ R. The distributed permutation flowshop scheduling problem[J]. Computers & Operations Research，2010，37(4)：754-768.
[26] 牟健慧. 基于混合遗传算法的车间逆调度方法研究[D]. 武汉：华中科技大学，2015. Mu Jianhui. Research on hybrid genetic algorithm based inverse job shop scheduling method[D]. Wuhan：Huazhong University of Science and Technology，2015.
[27] Lu Chao，Gao Liang，Yi Jin. Grey wolf optimizer with cellular topological structure[J]. Expert Systems with Applications，2018，107：89-114.
[28] 顾涛，李苏建，林莹璐，等. 周期式退火炉作批处理机的可重入批离散机流水车间调度[J]. 机械工程学报，2020，56(2)：220-232. GU Tao，LI Sujian，LIN Yinglu，et al. Periodic annealing furnace as batch processing machine reentrant batch discrete machine flow shop scheduling[J]. Journal of Mechanical Engineering，2020，56(2)：220-232.
[29] 牟健慧，潘全科，牟建彩，等. 基于遗传变邻域混合算法的带交货期的单机车车间逆调度方法[J]. 机械工程学报，2018，54(3)：148-159. Mu Jianhui，Pan Quanke，Mu Jiancai，et al. Inverse scheduling method for single locomotive workshop with due date based on genetic variable neighborhood hybrid algorithm[J]. Journal of Mechanical Engineering，2018，54(3)：148-159.
[30] Fu Yaping，Hou Yushuang ，Wang Zifan ， et al. Distributed scheduling problems in intelligent manufacturing systems[J]. Tsinghua Science and Technology，2021，26(5)：625-645.
[31] GAO K Z，HE Z M ，HUANG Y ，et al. A survey on meta-heuristics for solving disassembly line balancing，planning and scheduling problems in remanufacturing[J]，Swarm and Evolutionary Computation，2020，57：100719.
[32] PAN Quanke，GAO Liang，WANG Ling. An effective cooperative co-evolutionary algorithm for distributed flowshop group scheduling problems[J]. IEEE Transactions on Cybernetics，2020(99)：1-14.
[33] HUANG Yingying，PAN Quanke，HUANG Jiangping，et al. An improved iterated greedy algorithm for the distributed assembly permutation flowshop scheduling problem[J]. Computers & Industrial Engineering，2021，152：107021.