加工时间为区间数的两阶段流水生产鲁棒调度

doi:10.3778/j.issn.1002-8331.2206-0141

摘要/Abstract

摘要： 离散制造业中加工时间不确定的现象普遍存在，使得生产过程往往难以按照既定的调度方案来执行，而且难以实现满意的生产效果。研究在加工时间为区间数的环境下，以总完工时间为调度目标的两台机器流水生产鲁棒调度问题，旨在求解Min-Max准则的鲁棒调度方案。在详细描述该流水生产鲁棒调度问题的基础上，建立了问题的半无限数学规划模型。为降低求解复杂性，证明了问题的简化性质和占优性质，并设计了用于求解该问题的分支定界-遗传混合算法。仿真实验表明，提出的方法对该鲁棒调度问题具有很好的适用性。

关键词: 鲁棒调度, 两阶段流水生产, Min-Max准则, 总完工时间, 分支定界-遗传混合算法

Abstract: Since processing times are usually uncertain in discrete manufacturing industry, it is hard to implement production schedules as planned. The robust scheduling of two-stage flow shop with interval processing times is studied, which aims to solve robust schedules conformed to the Min-Max decision rule. The corresponding original scheduling problem is to minimize total completion times. Firstly, the robust scheduling problem is modeled as a semi-infinite programming formulation. Secondly, three theorems are proved and a hybrid algorithm is provided to combine branch-bound method and genetic algorithm, which contribute to solve the problem effectively and efficiently. At last, a computational experiment is conducted to illustrate the robust scheduling problem that can be solved through the modeling method and the hybrid algorithm proposed in this paper.

Key words: robust scheduling, two-stage flow shop, Min-Max decision rule, total completion times, branch and bound-genetic hybrid algorithm

张先超, 周泓. 加工时间为区间数的两阶段流水生产鲁棒调度[J]. 计算机工程与应用, 2023, 59(20): 266-273.

ZHANG Xianchao, ZHOU Hong. Robust Scheduling of Two-Stage Flow Shop with Interval Processing Times[J]. Computer Engineering and Applications, 2023, 59(20): 266-273.

参考文献

[1] 张先超，周泓.单机鲁棒调度多目标优化方法[J].计算机集成制造系统，2013，19（10）：2459-2466.
ZHANG X C，ZHOU H.Multi-objective optimization for robust single-machine scheduling[J].Computer Integrated Manufacturing Systems，2013，19（10）：2459-2466.
[2] JOO B J，SHIM S O，CHUA T J，et al.Multi-level job scheduling under processing time uncertainty[J].Computers & Industrial Engineering，2018，120（6）：480-487.
[3] AMIRI M F，BEHNAMIAN J.Multi-objective green flowshop scheduling problem under uncertainty：estimation of distribution algorithm[J].Journal of Cleaner Production，2020，251（4）：119734.
[4] 刘乐，朱洪利.双机流水车间外包与调度联合优化问题的混合变邻域搜索算法[J].计算机集成制造系统，2019，25（5）：1202-1222.
LIU L，ZHU H L.Hybrid variable neighborhood search algorithm for two-machine flow shop outsourcing and scheduling integrated optimization problem[J].Computer Integrated Manufacturing Systems，2019，25（5）：1202-1222.
[5] JING X L，PAN Q K，GAO L.Local search-based metaheuristics for the robust distributed permutation flowshop problem[J].Applied Soft Computing，2021，105（7）：107247.
[6] WANG B，WANG X Z，LAN F M，et al.A hybrid local-search algorithm for robust job-shop scheduling under scenarios[J].Applied Soft Computing，2018，62（1）：259-271.
[7] LIAO W Z，FU Y X.Min-max regret criterion-based robust model for the permutation flow-shop scheduling problem[J].Engineering Optimization，2020，52（4）：687-700.
[8] LEVORATO M，FIGUEIREDO R，FROTA Y.Exact solutions for the two-machine robust flow shop with budgeted uncertainty[J].European Journal of Operational Research，2022，300（1）：46-47.
[9] WU C，GUPTA J，CHENG S，et al.Robust scheduling for a two-stage assembly shop with scenario-dependent processing times[J].International Journal of Production Research，2020，6：5372-5387.
[10] 李成严，宋月，马金涛.模糊云资源调度问题的RIOPSO算法[J].计算机科学与探索，2021，15（8）：1534-1545.
LI C Y，SONG Y，MA J T.RIOPSO algorithm for fuzzy cloud resource scheduling problem[J].Journal of Frontiers of Computer Science and Technology，2021，15（8）：1534-1545.
[11] SUN Q，DOU J P，ZHANG C R.Robust optimization of flow shop scheduling with uncertain processing time[C]//Proceedings of 2020 IEEE International Conference on Mechatronics and Automation，Beijing，China，2020.
[12] CWIK M，JOZEFCZYK J.Heuristic algorithms for the minmax regret flow-shop problem with interval processing times[J].Central European Journal of Operations Research，2018，13（26）：215-238.
[13] ALLAHVERDI A，SOTSKOV Y.Two-machine flow shop minimum-length scheduling problem with random and bounded processing times[J].International Transactions in Operational Research，2003，10（1）：65-76.
[14] MATSVEICHUK N，SOTSKOV Y，WERNER F.The dominance digraph as a solution to the two-machine flow-shop problem with interval processing times[J].Optimization，2011，60（12）：1493-1517.
[15] WU C，BAI D Y，AZZOUZ A，et al.A branch-and-bound algorithm and four metaheuristics for minimizing total completion time for a two-stage assembly flow-shop scheduling problem with learning consideration[J].Engineering Optimization，2020，52（6）：1009-1036.
[16] CROCE F D，NARAYAN V，TADEI R.The two-machine total completion time flow shop problem[J].European Journal of Operational Research，1996，90（2）：227-237.
[17] 潘家文，钱谦，伏云发，等.最优权动态控制学习机制的多种群遗传算法[J].计算机科学与探索，2021，15（12）：2421-2437.
PAN J W，QIAN Q，FU Y F，et al.Multi-population genetic algorithm based on optimal weight dynamic control learning mechanism[J].Journal of Frontiers of Computer Science and Technology，2021，15（12）：2421-2437.
[18] 陈斌，刘卫国.基于SAC模型的改进遗传算法求解TSP问题[J].计算机科学与探索，2021，15（9）：1680-1693.
CHEN B，LIU W G.SAC model based improved genetic algorithm for solving TSP[J].Journal of Frontiers of Computer Science and Technology，2021，15（9）：1680-1693.