安装时间与次序相关的生产调度干扰管理研究

摘要/Abstract

摘要： 在安装时间和次序相关的单机调度问题中，为应对突发性的工件优先级变动造成的影响，构建了双目标重调度模型。原目标为生产的流程时间，扰动目标为工件的加工次序扰动。针对模型中的双目标，设计了基于有效解的两阶段混合启发式算法进行求解，在原目标和扰动目标之间进行权衡。混合算法第一阶段里，基于任意单个工件次序变化将双目标问题转化成单目标TSP问题，利用最近邻域和插入混合求得单目标问题的若干解，构成初始种群。第二阶段中基于非支配排序遗传算法在处理多目标问题上的优势，对初始种群进行扩展搜索，最后输出问题的有效前沿。通过数值试验运算比较分析若干针对有效解集的指标，验证了混合算法求得的解集在多样性和临近性上要优于单纯的非支配排序遗传算法。该混合算法可以有效地解决具有安装时间的加工次序扰动问题。

关键词: 重调度, 次序扰动, 双目标, 有效前沿, 非支配排序遗传算法

Abstract: In this paper, a disruption management problem on single machine scheduling with sequence dependent setup times 1|s_ij|C_max is studied. It is originated from practical situations where jobs come from different job families, and during the implementation of initial schedule the priority of certain job would be suddenly upgraded, causing disruption to the original plan. This makes it necessary to consider jobs' sequence deviation from original plan during rescheduling, which is calculated based on job i's relative position to job j in the revised schedule. In this paper, a bi-objective rescheduling model is built, considering both C_max and sequence deviation. In order to effectively solve the model, local search is combined with global search and a two-stage approach is designed. In stage 1 construction heuristic based on mixed Nearest Neighbor and Insertion is used to obtain good initial solutions for stage 2 to make extension search along the Pareto front. Computational study shows that the proposed approach outperforms the widely applied NSGA-Ⅱ in both proximity and diversity metrics. And for decision-makers, better decision alternatives could be provided for the trade-off between production cost and deviation of disruption. The research sets an example for applying hybrid metaheuristic to deal with disruption in machine scheduling and computational results could serve as comparison for further studies of this problem.

Key words: rescheduling, sequence disruption, bi-criterion, Pareto front, NSGA-Ⅱ

中图分类号:

C931

刘锋, 王建军, 饶卫振, 杨德礼. 安装时间与次序相关的生产调度干扰管理研究[J]. 中国管理科学, 2014, 22(1): 45-54.

LIU Feng, WANG Jian-jun, RAO Wei-zhen, YANG De-li. Machine Scheduling Disruption Management with Sequence Dependent Setup Times[J]. Chinese Journal of Management Science, 2014, 22(1): 45-54.

参考文献

[1] 唐立新, 黄琳. 调整时间与顺序相关的flowshop调度的精确算法[J]. 系统工程学报, 2002, 17(04): 309-315.
[2] Kuo W H, Hsu C J, Yang D L. Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects[J]. Computers & Industrial Engineering, 2011, 61(1): 179-183.
[3] Wang Jianjun, Wang Jibo, Liu F. Parallel machines scheduling with a deteriorating maintenance activity[J]. Journal of the Operational Research Society, 2011, 62(10): 1898-1902.
[4] Hall N G, Potts C N. Rescheduling for new orders[J]. Operations Research, 2004, 52(3): 440-453.
[5] Qi Xiangtong, Bard J F, Yu Gang. Disruption management for machine scheduling: The case of SPT schedules[J]. International Journal of Production Economics, 2006, 103(1): 166-184.
[6] Hall N G, Potts C N. Rescheduling for job unavailability[J]. Operations Research, 2010, 58(3): 746-755.
[7] Zhao Chuanli, Tang Hengyong. Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs[J]. Computers & Industrial Engineering, 2010, 59(4): 663-666.
[8] Cheng T, Lee W C, Wu C C. Scheduling problems with deteriorating jobs and learning effects including proportional setup times[J]. Computers & Industrial Engineering, 2010, 58(2SI): 326-331.
[9] Bahalke U, Yolmeh A M, Shahanaghi K. Meta-heuristics to solve single-machine scheduling problem with sequence-dependent setup time and deteriorating jobs[J]. International Journal of Advanced Manufacturing Technology, 2010, 50(5-8): 749-759.
[10] Ouelhadj D, Petrovic S. A survey of dynamic scheduling in manufacturing systems[J]. Journal of Scheduling, 2009, 12(4): 417-431.
[11] Gurel S, Korpeoglu E, Akturk M S. An anticipative scheduling approach with controllable processing times[J]. Computers & Operations Research, 2010, 37(6): 1002-1013.
[12] Ozlen M, Azizoglu M. Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria[J]. Journal of the Operational Research Society, 2011, 62(1): 152-164.
[13] Lee C Y, Leung J, Yu Gang. Two machine scheduling under disruptions with transportation considerations[J]. Journal of Scheduling, 2006, 9(1): 35-48.
[14] Yuan Jinjiang, Mu Yundong. Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption[J]. European Journal of Operational Research, 2007, 182(2): 936-944.
[15] Yuan Jinjiang, Mu Yundong, Lu Lingfa, et al. Rescheduling with release dates to minimize total sequence disruption under a limit on the makespan[J]. ASIA-Pacific Journal of Operational Research, 2007, 24(6): 789-796.
[16] Al-Hinai N, Elmekkawy T Y. Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm[J]. International Journal of Production Economics, 2011, 132(2): 279-291.
[17] Pinedo M L. Scheduling: Theory, algorithms, and systems[M]. New York: Springer Science+Business Media, 2008.
[18] 张明玺, 李昆鹏. 混合离散差分进化算法在单机批处理调度中的应用[J]. 中国管理科学, 2010, 8(04): 114-123.
[19] 李铁克, 苏志雄. 炼钢连铸生产调度问题的两阶段遗传算法[J]. 中国管理科学, 2009, 17(05): 68-74.
[20] 程八一, 陈华平, 王栓狮. 基于微粒群算法的单机不同尺寸工件批调度问题求解[J]. 中国管理科学, 2008, 16(03): 84-88.
[21] Li Binbin, Wang Ling. A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2007, 37(3): 576-591.
[22] 张超勇, 董星, 王晓娟, 等. 基于改进非支配排序遗传算法的多目标柔性作业车间调度[J]. 机械工程学报, 2010, 46(11): 156-164.
[23] Srinivas N, Deb K. Muiltiobjective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary Computation, 1994, 2(3): 221-248.
[24] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[25] 饶卫振, 金淳, 黄英艺. 求解TSP问题的最近邻域与插入混合算法[J]. 系统工程理论与实践, 2011, 31(8): 1419-1428.
[26] 罗辞勇, 陈民铀, 张聪誉. 采用循环拥挤排序策略的改进NSGA-Ⅱ算法[J]. 控制与决策, 2010, 25(02): 227-231.
[27] 毕晓君, 肖婧. 基于自适应差分进化的多目标进化算法[J]. 计算机集成制造系统, 2011, 17(12): 2660-2665.
[28] 张美华, 李爱平, 徐立云. 基于Pareto最优的多企业协同计划调度优化[J]. 中国机械工程, 2012, 23(05): 563-569.
[29] Hall N G, Posner M E. Generating experimental data for computational testing with machine scheduling applications[J]. Operations Research, 2001, 49(6): 854-865.