多目標多約束混合流水車間插單重調度問題研究

摘要: 研究了多目標多階段混合流水車間的緊急訂單插單重調度問題，綜合考慮工件批量、刀具換裝時間、運輸能力等約束。先以最小化訂單完工時間和最小化總運輸時間為雙目標建立靜態初始訂單調度模型，再針對緊急訂單插單干擾，增加最小化總加工機器偏差值目標，建立三目標重調度優化模型，并分別用NSGA-II算法與融合基于事件驅動的重調度策略和重排插單策略的NSGA-III算法對兩個模型進行求解。最后，以某實際船用管類零件生產企業為案例，先對NSGA-II算法和NSGA-III算法的性能進行評估，得到NSGA-II算法更適用于解決雙目標優化問題而NSGA-III算法在解決三目標優化問題時表現更優的結論，再將所建模型與所提算法應用于該企業的十組插單案例中，所得優化率接近三分之一，驗證了實用性和有效性。
- 混合流水車間 /
- 緊急訂單插單重調度 /
- 多目標 /
- 多約束 /
- NSGA-III算法
Abstract: To study the multi-objective rush order insertion rescheduling problem under hybrid flow shop with multiple stages and multiple machines, the constraints, such as job lots, sequence-dependent set-up times, and round-trip transportation times, were simultaneously considered. A static optimal scheduling model of initial orders was first established to minimize the maximum order completion time and minimize the total transportation time. The non-dominated sorting genetic algorithm (NSGA)-II algorithm was applied to solve a two-objective optimal problem. Then, for the rush order insertion disturbance factor, the objective to minimize the total machine deviation between the initial scheduling and rescheduling plans was added as a stability index to establish an optimal rush order rescheduling model. The NSGA-III algorithm based on the event-driven rescheduling strategy and order rearrangement strategy was applied to solve a three-objective optimal problem. Finally, a realistic ship pipe parts manufacturing enterprise is regarded as a study case. Two sets of experiments are carried out to explain the motivation of the selected method. The performances of the NSGA-II and NSGA-III algorithms are evaluated by three metrics, including the mean ideal distance, spread of non-dominated solution, and percentage of domination. The results show that the NSGA-II algorithm is more suitable for solving two-objective optimal problem, whereas NSGA-III algorithm performs better in solving three-objective optimal problems. Then, the proposed model and method were applied to 10 rush order insertion cases of the enterprise. All the three objectives were improved according to the compared results obtained by the actual and optimal scheduling. The optimal rate is close to one third, which verifies the feasibility of the proposed model and the effectiveness of the proposed method. The proposed model and method may assist other enterprises that apply make-to-order production mode to reduce the impact of rush order insertion and realize a win-win mechanism between enterprises and customers.
- hybrid flow shop /
- rush order insertion rescheduling /
- multi-objective /
- multi-constraint /
- NSGA-III algorithm

HTML全文

圖 1 雙層編碼與解碼（a）和個體交叉（b）示意圖

Figure 1. Double encoding and decoding mechanism (a) and example of crossover operator (b)

下載: 全尺寸圖片幻燈片

圖 2 生產車間布局圖

Figure 2. Layout of the shop

下載: 全尺寸圖片幻燈片

圖 3 兩種算法所得初始訂單優化調度的Pareto最優解集. （a）NSGA-II算法; （b）NSGA-III算法

Figure 3. Pareto optimal solutions of the initial order: (a) NSGA-II algorithm; (b) NSGA-III algorithm

下載: 全尺寸圖片幻燈片

圖 4 兩種算法所得插單后所有工件調度的Pareto最優解集. （a）NSGA-II算法; （b）NSGA-III算法

Figure 4. Pareto optimal solutions of all unfinished jobs: (a) NSGA-II algorithm; (b) NSGA-III algorithm

下載: 全尺寸圖片幻燈片

圖 5 企業實際調度和NSGA-II算法優化調度結果的雙目標對比圖. （a）初始訂單總完工時間; （b）總運輸時間

Figure 5. Compare of two objectives obtained by the actual and the optimal initial order scheduling: (a) total completion time; (b) transportation time

下載: 全尺寸圖片幻燈片

圖 6 企業實際調度和NSGA-III算法優化調度結果的三目標對比圖. （a）插單后總完工時間; （b）總運輸時間; （c）總機器偏差

Figure 6. Compare of three objectives obtained by the actual and the optimal rush order insertion rescheduling: (a) total completion time; (b) total transportation time; (c) total machine deviation

下載: 全尺寸圖片幻燈片

${P_{ijm}}$：	單個工件${O_i}$在階段j的機器m上的加工時間；
${P_{ijm,x}}$：	整批工件${O_i}_{,x}$在階段j的機器m上的加工時間；
${S_{ijm,x}}$：	工序${O_{ij}}_{,x}$在機器m上的開始加工時間；
${F_{ijm,x}}$：	工序${O_{ij}}_{,x}$在機器m上的完工時間；
${\rm{Se}}{{\rm{t}}_{ijm,x}}$：	工序${O_{ij}}_{,x}$在機器m上的刀具換裝時間；
${\rm{Se}}{{\rm{t}}_m}$：	機器m的刀具換裝時間；
${\rm{M}}{{\rm{T}}_{{m_1},{m_2}}}$：	機器${m_1}$與${m_2}$間的運輸時間，${m_1} \in {M_j},{m_2} \in {M_{^{{(_{j{\rm{ + }}1}})}}}$；
${\rm{S}}{{\rm{T}}_{ij(j + 1),x,v}}$：	運送設備v將整批工件${O_i}_{,x}$從階段j運到階段$(j+1)$的開始運輸時間；
${\rm{F}}{{\rm{T}}_{ij(j + 1),x,v}}$：	運送設備v將整批工件${O_i}_{,x}$從階段j運到階段$(j+1)$的運輸完成時間；
${J_{{O_{a,b}} \to {O_{i,x}},jm}}$：	0-1決策變量，若為1，則在階段j的機器m上，工件${O_{a,b}}$為工件${O_i}_{,x}$的上一批加工工件；
${K_{{O_{e,f}} \to {O_{i,x}}}}_{,j(j + 1),v}$：	0-1決策變量，若為1，則運送設備v在階段j與階段$(j+1)$間，工件${O_{e,f}}$為工件${O_i}_{,x}$的上一批運送工件；
${X_{ijm,x}}$：	0-1決策變量，若為1，則整批工件${O_i}_{,x}$在階段j的機器m上加工；
${T_{ij(j + 1),x,v}}$：	0-1決策變量，若為1，則工序${O_{ij}}_{,x}$由運輸設備v從階段j運到階段$(j+1)$；
${Y_{ajm,b - ijm,x}}$：	0-1決策變量，若為1，則${J_{{O_{a,b}} \to {O_{i,x}},jm}}$為1，且${O_{a,b}}$與${O_i}_{,x}$為不同種類工件，，即$a \ne i$。

下載: 導出CSV

表 1 零件最優生產批量和工藝路線表

Table 1. Optimal lot sizing and routing of each job

零件類型	最優生產批量	切割	彎管	點焊	全焊	打磨	泵壓
1	16	[1, 2]	[14]	[16, 17]	[18, 19]	[20, 21]	[22]
2	40	[3, 4, 5]	[15]	[16, 17]	[18, 19]	[20, 21]	[22]
3	16	[1, 2]	[6, 7]	[16, 17]	[18, 19]	[20, 21]	[22]
4	64	[3, 4, 5]	[8]	[16, 17]	[18, 19]	[20, 21]	[22]
5	32	[3, 4, 5]	[9]	[16, 17]	[18, 19]	[20, 21]	[22]
6	32	[3, 4, 5]	[10]	[16, 17]	[18, 19]	[20, 21]	[22]
7	50	[3, 4, 5]	[11, 12]	[16, 17]	[18, 19]	[20, 21]	[22]
8	100	[3, 4, 5]	[13]	[16, 17]	[18, 19]	[20, 21]	[22]

下載: 導出CSV

表 2 緊急訂單插單信息表

Table 2. Information of the rush order insertion case

初始訂單（2018/04/18 8:00）		緊急訂單（2018/04/18 11:00）
零件類型	加工數量	零件類型	加工數量
1	16	1	32
2	72	2	0
3	0	3	0
4	60	4	64
5	0	5	0
6	30	6	0
7	0	7	100
8	90	8	80

下載: 導出CSV

表 3 NSGA-II和NSGA-III算法對初始訂單調度的評價指標對比表

Table 3. Comparison of three indications obtained by NSGA-II and NSGA-III that applied to solve initial order scheduling problem

算法	MID	SNS	POD
NSGA-II	912.89	24790.13	0.63
NSGA-III	1239.21	24976.66	0.37

下載: 導出CSV

表 4 NSGA-II和NSGA-III算法對緊急訂單插單重調度問題的評價指標對比表

Table 4. Comparison of three indications obtained by NSGA-II and NSGA-III that applied to solve ROIRP

算法	MID	SNS	POD
NSGA-II	1474.68	24904.33	0.32
NSGA-III	548.24	25036.51	0.68

下載: 導出CSV

www.77susu.com

參考文獻(16)

[1]	Gupta J N D. Two-stage, hybrid flowshop scheduling problem. J Operational Res Soc, 1988, 39(4): 359 doi: 10.1057/jors.1988.63
[2]	Meng T, Pan Q K, Li J Q, et al. An improved migrating birds optimization for an integrated lot-streaming flow shop scheduling problem. Swarm Evolutionary Comput, 2018, 38: 64 doi: 10.1016/j.swevo.2017.06.003
[3]	Rossi A. Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships. Int J Prod Economics, 2014, 153: 253 doi: 10.1016/j.ijpe.2014.03.006
[4]	Yue L, Guan Z L, Zhang L, et al. Multi-objective lotsizing and scheduling with material constraints in flexible parallel lines using a Pareto based guided artificial bee colony algorithm. Comput Ind Eng, 2019, 128: 659 doi: 10.1016/j.cie.2018.12.065
[5]	Qin H B, Fan P F, Tang H T, et al. An effective hybrid discrete grey wolf optimizer for the casting production scheduling problem with multi-objective and multi-constraint. Comput Ind Eng, 2019, 128: 458 doi: 10.1016/j.cie.2018.12.061
[6]	Vieira G E, Herrmann J W, Lin E. Rescheduling manufacturing systems: a framework of strategies, policies, and methods. J Scheduling, 2003, 6(1): 39 doi: 10.1023/A:1022235519958
[7]	Wu S D, Storer R H, Pei C C. One-machine rescheduling heuristics with efficiency and stability as criteria. Comput Operations Res, 1993, 20(1): 1 doi: 10.1016/0305-0548(93)90091-V
[8]	Cui Z, Gu X S. A discrete group search optimizer for hybrid flow-shop scheduling problem with random breakdown. Math Probl Eng, 2014, 24: 621393
[9]	Wang K, Choi S H. A decomposition-based approach to flexible flow shop scheduling under machine breakdown. Int J Prod Res, 2012, 50(1): 215 doi: 10.1080/00207543.2011.571456
[10]	Gao K Z, Suganthan P N, Pan Q K, et al. Artificial bee colony algorithm for scheduling and rescheduling fuzzy flexible job shop problem with new job insertion. Knowledge-Based Syst, 2016, 109: 1 doi: 10.1016/j.knosys.2016.06.014
[11]	Chiu Y F, Shih C J. Rescheduling strategies for integrating rush orders with preventive maintenance in a two-machine flow shop. Int J Prod Res, 2012, 50(20): 5783 doi: 10.1080/00207543.2011.627887
[12]	Wang D J, Liu F, Wang J J, et al. Integrated rescheduling and preventive maintenance for arrival of new jobs through evolutionary multi-objective optimization. Soft Comput, 2016, 20(4): 1635 doi: 10.1007/s00500-015-1615-7
[13]	Pei H Y, Jiang Z H, Hu J W, et al. Integrating rescheduling with preventive maintenance in the flow-shop problem under rush order. Ind Eng Manage, 2017, 22(1): 50 裴海燕, 蔣祖華, 胡家文, 等. 插單擾動下流水線生產與維護的重調度優化. 工業工程與管理, 2017, 22(1):50
[14]	Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based non-dominated sorting approach, Part I: solving problems with box constraints. IEEE Trans Evolutionary Comput, 2014, 18(4): 577 doi: 10.1109/TEVC.2013.2281535
[15]	Qi X T, Bard J F, Yu G. Disruption management for machine scheduling: the case of SPT schedules. Int J Prod Economics, 2006, 103(1): 166 doi: 10.1016/j.ijpe.2005.05.021
[16]	Govindan K, Jafarian A, Khodaverdi R, et al. Two-echelon multiple-vehicle location–routing problem with time windows for optimization of sustainable supply chain network of perishable food. Int J Prod Economics, 2014, 152: 9 doi: 10.1016/j.ijpe.2013.12.028