﻿ 具有恶化效应的新工件到达生产调度干扰管理
 文章快速检索 高级检索

Disruption management for multiple new orders in production scheduling with deteriorating processing time
WANG Du-juan, WANG Jian-jun, LIU Chun-lai, WANG Yan-zhang
School of Management Science and Engineering, Dalian University of Technology, Dalian 116024, China
Abstract:In single machine scheduling with deteriorating processing time, we study the problem of dealing with the arrival of multiple unexpected orders. We build up the bi-objective model where original objective is based on system operational cost, while the deviation objective is based on the delay of job's completion time with respect to its original completion time. In order to effectively solve the model, we combine simulated annealing-based multi-objective optimization algorithm, which is good at jumping out of local optimality, with non-dominated sorting genetic algorithm, which is good at fast converging to Pareto front. And we design a hybrid algorithm to balance between exploration and exploitation. By analyzing the Pareto optimal property, we could further effectively narrow the searching space of hybrid algorithm, speeding up convergence and improving Pareto front quality. Finally, by randomly generating and solving numerical problem instances, we show that our hybrid algorithm is effective for the disruption management problem, and Pareto optimal property could significantly improve the performance of hybrid algorithm.
Key words: deteriorating effect     disruption management     Pareto optimal solution     hybrid meta-heuristics

0 引言

 $${f_1} = \sum {{C_j}\left( \sigma \right)} = \sum\limits_{j = 1}^{{n_O} + {n_N}} {\left( {p_j^A\left( \sigma \right) + {t_j}\left( \sigma \right)} \right)}$$ (1)

 $${f_2} = \sum {{T_j}\left( \sigma \right)} = \sum\limits_{j = 1}^{{n_O}} {\max\left\{ {{C_j}\left( \sigma \right) - {{\bar C}_j},0} \right\}}$$ (2)

 $$\left. 1 \right|\left. {{p_j}\left( {a + b{t_j}} \right)} \right|\sum {{C_j}\left( \sigma \right)} ,\sum {{T_j}\left( \sigma \right)}$$ (3)
2 问题Pareto最优解特性分析

$C_{\max} \left( \sigma \right) = t\mathop \prod \limits_{j = 1}^n \left( {1 + bp_j } \right) + \frac{a}{b}\left( {\mathop \prod \limits_{j = 1}^n \left( {1 + bp_j } \right) - 1} \right),$

$\sum {{C_j}\left( \sigma \right)} = t\mathop \sum \limits_{j = 1}^n \mathop \prod \limits_{i = 1}^j \left( {1 + b{p_i}} \right) + \mathop \sum \limits_{j = 1}^n \frac{a}{b}\left( {\mathop \prod \limits_{i = 1}^j \left( {1 + b{p_i}} \right) - 1} \right).$

①交换$J_j$与$J_i$的位置构造新加工时间表$\tilde \sigma$,那么 ${C_i}\left( {\tilde \sigma } \right) = {t_0} + {p_i}\left( {a + b{t_0}} \right) < {C_j}\left( {{\sigma ^*}} \right)$, $\widetilde{J_1},\widetilde{J_2 },\cdots,\widetilde{J_h }$在$\tilde \sigma$中完工时间小于在$\sigma ^\ast$中完工时间. 又由引理1,$C_j \left( \tilde \sigma \right) = C_i \left( {\sigma ^\ast } \right)$. 于是交换位置后所有工件完工时间和变小.

②对于扰动目标,如果$T_i \left( \tilde \sigma \right) > 0$,那么当$T_j \left( {\sigma ^\ast } \right) > 0$时,$\left( {T_j \left( \tilde \sigma \right) + T_i \left( \tilde \sigma \right)} \right) - \left( {T_j \left( {\sigma ^\ast } \right) + T_i \left( {\sigma ^\ast } \right)} \right) = C_j \left( \tilde \sigma \right) - C_i \left( {\sigma ^\ast } \right) + C_i \left( \tilde \sigma \right) - C_j \left( {\sigma ^\ast } \right) < 0$; 当$T_j \left( {\sigma ^\ast } \right) = 0$时,$\left( {T_j \left( \tilde \sigma \right) + T_i \left( \tilde \sigma \right)} \right) - T_i \left( {\sigma ^\ast } \right) = C_j \left( \tilde \sigma \right) - C_j \left( {\pi ^\ast } \right) + C_i \left( \tilde \sigma \right) - C_i \left( {\sigma ^\ast } \right) < C_j \left( {\sigma ^\ast } \right) - C_j \left( {\pi ^\ast } \right) < 0$.

HMHA种群进化过程中以向量$\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\rightharpoonup$}} \over x} = \left\{ {{x_1},{x_2},{x_3},\cdots ,{x_{{n_O} + {n_N}}}} \right\}$作为种群个体,采用基于$n_O + n_N$个工件位置的整数编码方式,其中$x_i$对应个体染色体的第$i$个基因,代表工件$J_i \in J$在加工时间表中的位置,$1\le x_i \le n_O + n_N$,且当$i \ne j$时,$x_i \ne x_j$,$i,j = 1,2,\cdots ,n_O + n_N$.

HMHA的流程图如图 1所示,具体实现步骤如下:

 图 1 HMHA的流程图

NSGA-II在多目标优化前提下,采取非支配排序方法保证种群的多样性和与最优有效前沿的邻近性. 非支配排序方法包括有效前沿的划分和适应度值的分配[24]

①具有恶化效应的单机不可中断生产调度过程中,当新工件到达时, 最简单的处理方式是将新工件排列于已有加工时间表中旧工件后边进行加工, 此时不会产生系统扰动,但加工成本通常较高, 因此需要调整已有加工时间表; ②为降低加工成本, 可以将所有工件按照SPT规则排序加工,此时加工成本最低, 但系统扰动可能较大; ③应对新工件到达事件的理想加工时间表中新旧工件分别具有一定的SPT规则特性, 可以作为制定简单应对策略的理论指导. 5 结论

(1)本文以加工制造企业在恶化效应下的生产调度为背景,研究单机环境下的新工件到达干扰管理问题,在恶化效应普遍存在于生产加工过程这一客观情境下,考虑优化加工成本的同时,充分注重系统扰动对生产调度过程的影响,避免延迟造成较多的扰动费用及客户满意度影响,使决策者可以在加工成本与系统扰动间权衡选择,使理论研究更加符合生产实际. 决策者可以根据问题求解得出的有效前沿,在加工成本和系统扰动之间权衡选择,提出有效的干扰应对策略,从而充分降低企业的加工成本和系统扰动,全面提升企业经济效益和管理水平.

(2)本文结合已有元启发式算法NSGA-II和AMOSA的各自优势, 设计混合元启发式算法HMHA对本文的干扰管理问题求解,并在此基础上, 引入分析得出的问题Pareto最优解特性构造HMHA-OSF算法. 通过设计随机生成数值实验, 结合度量有效前沿收敛性和多样性的公认指标结果分析,验证了HMHA比 NSGA-II在求解该类问题时具有更好的收敛能力和有效前沿质量, 以及引入Pareto最优解特性的HMHA-OSF比HMHA在算法性能上的进一步改进, 体现设计的HMHA比已有主流算法更加快速高质量的求解问题, 以及分析得出的问题Pareto最优解特性的科学合理性及其在指导算法进行快速有效求解时发挥的重要作用.

(3)本文设计的混合元启发式算法能快速有效求解问题, 进一步证明了算法混合的思想是提高算法优化性能的一个有效途径；该混合元启发式算法可以供相关领域多目标优化问题求解时使用或作为算法设计的参照；该算法的混合策略及设计思路可以作为设计其他混合元启发式算法的策略借鉴和技术参考, 并有助于推动元启发式算法领域的发展。

(4)本文通过对问题的Pareto最优解特性进行分析,进而将其引入算法设计过程以有效提升算法性能这一问题求解思路,不同于已有研究中使用元启发式算法直接对问题进行求解的方式,表现出快速高效的问题求解能力,这一求解问题的新思路可以为其他干扰管理问题的求解提供参照.

 [1] Cowling P, Johansson M. Using real time information for effective dynamic scheduling[J]. European Journal of Operational Research, 2002, 139(2): 230-244. [2] Aytug H, Lawley M A, McKay K, et al. Executing production schedules in the face of uncertainties: A review and some future directions[J]. European Journal of Operational Research, 2005, 161(1): 86-110. [3] 胡祥培, 张漪, 丁秋雷, 等. 干扰管理模型及其算法的研究进展[J]. 系统工程理论与实践, 2008, 28(10): 40-46.Hu Xiangpei, Zhang Yi, Ding Qiulei, et al. Review on disruption management model and its algorithm[J]. Systems Engineering —— Theory & Practice, 2008, 28(10): 40-46. [4] 唐恒永, 唐春晖, 赵传立. 突发事件应急管理中的中断-继续随机排序模型[J]. 系统工程理论与实践, 2010, 30(4): 751-757.Tang Hengyong, Tang Chunhui, Zhao Chuanli. A preemptive-resume stochastic scheduling model with disruption[J]. Systems Engineering —— Theory & Practice, 2010, 30(4): 751-757. [5] 李巧云, 王冰, 王晓明. 随机机器故障下单机预测调度方法[J]. 系统工程理论与实践, 2011, 31(12): 2387-2393.Li Qiaoyun, Wang Bing, Wang Xiaoming. Predictable scheduling approach for single machine subject to random machine breakdown[J]. Systems Engineering —— Theory & Practice, 2011, 31(12): 2387-2393. [6] Hall N G, Potts C N. Rescheduling for new orders[J]. Operations Research, 2004, 52(3): 440-453. [7] Lee C Y, Leung J, Yu G. Two machine scheduling under disruptions with transportation considerations[J]. Journal of Scheduling, 2006, 9(1): 35-48. [8] 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. [9] Katragjini K, Vallada E, Ruiz R. Flow shop rescheduling under different types of disruption[J]. International Journal of Production Research, 2013, 51(3): 780-797. [10] He W, Sun D H. Scheduling flexible job shop problem subject to machine breakdown with route changing and right-shift strategies[J]. International Journal of Advanced Manufacturing Technology, 2013, 66(1-4): 501-514. [11] Qi X T, Bard J F, Yu G. Disruption management for machine scheduling: The case of SPT schedules[J]. International Journal of Production Economics, 2006, 103(1): 166-184. [12] Liu F, Wang J J, Yang D L. Solving single machine scheduling under disruption with discounted costs by quantum-inspired hybrid heuristics[J]. Journal of Manufacturing Systems, 2013, 32(4): 715-723. [13] Akturk M S, Atamturk A, Gurel S. Parallel machine match-up scheduling with manufacturing cost considerations[J]. Journal of Scheduling, 2010, 13(1): 95-110. [14] 刘锋, 王征, 王建军, 等. 加工能力受扰的可控排序干扰管理[J]. 系统管理学报, 2013, 22(4): 505-512.Liu Feng, Wang Zheng, Wang Jianjun, et al. Disruption management in scheduling with controllable and disrupted processing capability[J]. Journal of Systems & Management, 2013, 22(4): 505-512. [15] Zhao C L, Tang H Y. Rescheduling problems with deteriorating jobs under disruptions[J]. Applied Mathematical Modelling, 2010, 34(1): 238-243. [16] Zhao C L, Zhang Q L, Tang H Y. Scheduling problems under linear deterioration[J]. Acta Automatica Sinica, 2003, 29(4): 531-535. [17] Zhang X G, Wang Y. Rescheduling problems with agreeable job parameters to minimize the tardiness costs under deterioration and disruption[J]. Mathematical Problems in Engineering, 2013: 1-7. [18] Liu L, Zhou H. Single-machine rescheduling with deterioration and learning effects against the maximum sequence disruption[J]. International Journal of Systems Science, 2014. doi:10.1080/00207721.2013.876519. [19] Xiong J, Xing L N, Chen Y W. Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns[J]. International Journal of Production Economics, 2013, 141(1): 112-126. [20] Pinedo M L. Scheduling: Theory, algorithms, and systems[M]. 3rd ed. New York: Springer, 2008: 50-54. [21] Zhao Q L, Yuan J J. Pareto optimization of rescheduling with release dates to minimize makespan and total sequence disruption[J]. Journal of Scheduling, 2013, 16(3): 253-260. [22] Kononov A, Gawiejnowicz S. NP-hard cases in scheduling deteriorating jobs on dedicated machines[J]. Journal of the Operational Research Society, 2001, 52(6): 708-717. [23] Siinivas N, Deb K. Multiobjective 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-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. [25] 张超勇, 董星, 王晓娟, 等.基于改进非支配排序遗传算法的多目标柔性作业车间调度[J]. 机械工程学报, 2010, 46(11): 156-164.Zhang Chaoyong, Dong Xing, Wang Xiaojuan, et al. Improved NSGA-II for the multi-objective flexible job-shop scheduling problem[J]. Journal of Mechanical Engineering, 2010, 46(11): 156-164. [26] Bandyopadhyay S, Saha S, Maulik U, et al. A simulated annealing-based multiobjective optimization algorithm: AMOSA[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(3): 269-283. [27] Sengupta S, Bandyopadhyay S. De Novo design of potential RecA inhibitors using multiobjective optimization[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2012, 9(4): 1139-1154. [28] Wang K, Choi S H, Qin H, et al. A cluster-based scheduling model using SPT and SA for dynamic hybrid flow shop problems[J]. International Journal of Advanced Manufacturing Technology, 2013, 67(9-12): 2243-2257. [29] 王凌. 智能优化算法及其应用[M]. 北京: 清华大学出版社, 2001.Wang Ling. Intelligent optimization algorithm and its application[M]. Beijing: Tsinghua University Press, 2001. [30] Suman B, Kumar P. A survey of simulated annealing as a tool for single and multiobjective optimization[J]. Journal of the Operational Research Society, 2006, 57(10): 1143-1160. [31] Kirkpatrick S, Gelatt C D J, Vecchi M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598): 671-680. [32] Li B, Wang L. 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. [33] Vidal T, Crainic T G, Gendreau M, et al. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems[J]. Operations Research, 2012, 60(3): 611-624.
0

#### 文章信息

WANG Du-juan, WANG Jian-jun, LIU Chun-lai, WANG Yan-zhang

Disruption management for multiple new orders in production scheduling with deteriorating processing time

Systems Engineering - Theory & practice, 2015, 35(2): 368-380.