Order acceptance and scheduling on parallel machines with setup time and machine-eligibility constraints
-
摘要: 訂單接受與不相關并行機調度是訂單接受與訂單調度的聯合決策, 廣泛存在于面向定制的多品種混合生產環境中. 針對這一問題, 考慮了順序與機器依賴的安裝時間以及可加工機器限制, 并以最小化總成本為優化目標. 其中, 總成本由被接受訂單的總拖期成本和被拒絕訂單的總拒絕成本構成. 通過分析訂單拒絕對目標的影響, 提出了列表拒絕方法和訂單拒絕規則, 進而設計了協同進化遺傳算法. 算法將染色體編碼分解為訂單列表和訂單指派兩個個體, 提出了基于列表拒絕方法的解碼方案來進行訂單拒絕決策. 由于兩個個體相互獨立, 且二者的進化約束不同, 因而引入協同進化策略, 并根據個體的編碼特征, 分別采用單親遺傳算子和傳統遺傳算子進行遺傳操作. 數據實驗驗證了算法的有效性和求解效率, 并對問題規模和訂單拒絕成本對算法性能的影響進行了分析.Abstract: Integration of order acceptance and scheduling on unrelated parallel machines is a joint decision problem, and arise from the multi-variety customized production environment, which usually has the following characteristics. First, there are a number of parallel machines (production lines), each of which can only produce a limited variety of products referred as the machine-eligibility constraint. Second, the processing technologies of various machines differ; thus, these parallel machines are unrelated. Third, because the machines are unrelated, the setup time of an order is related not only to the order sequence but also to the machine used, which is called a sequence-and machine-dependent setup time. To minimize total cost, this study investigates the scheduling problems posed by order acceptance and unrelated parallel machines with setup time and machine-eligibility constraints. In this problem, an order has two options, rejection or acceptance. If an order is rejected, it generates a rejection cost. Otherwise, the order process must be completed before the due date, or there will be a tardiness cost. Therefore, the total cost spent is calculated as the sum of the total rejection cost of rejected orders and total weighted tardiness cost of accepted orders. To solve this problem, the effect of rejecting an order on the total cost was analyzed, and a list of rejecting methods and rejection rules were proposed. Furthermore, a cooperative coevolving genetic algorithm (CCGA) was developed. In this CCGA, an encoding scheme was proposed that divides chromosomes into two subsets corresponding to the order list and order assignment. Moreover, a list-rejecting-based decoding procedure was presented for deciding rejection for a chromosome. As the two subsets are independent of each other and their evolutionary constraints are essentially different, a cooperative coevolution strategy was applied to evolve the subpopulations of these subsets using partheno-genetic and traditional genetic operators. Computational experiments on a large set of randomly generated instances were performed to verify the effectiveness and efficiency of this algorithm. Additionally, the impacts of problem size and rejection cost were studied experimentally. The results reveal that in the majority of cases characterized by various problem sizes and rejection costs, the proposed algorithm performs effectively and efficiently.
-
表 1 CPLEX與CCGA的實驗結果
Table 1. Experimental results for CPLEX and CCGA
m t(n) CPLEX CCGA m t(n) CPLEX CCGA Avg. Time/s Avg. Opt./% Time/s Avg. Time/s Avg. Opt./% Time/s 2 2(4) 0 0.072 0.9 70 0.022 3 4(12) 0.8 0.106 1.6 80 0.077 3(6) 0.7 0.069 2.1 60 0.036 4 2(8) 2.1 0.086 2.1 100 0.055 4(8) 0.8 0.084 2.8 70 0.048 3(12) 1.6 0.106 1.6 100 0.081 3 2(6) 0 0.069 0.5 80 0.036 4(16) 0.8 0.220 3.2 70 0.109 3(9) 0.1 0.077 0.8 90 0.056 平均值 0.77 0.099 1.73 80 0.058 
下載: 導出CSV
表 2 4種算法求解每組算例的總成本均值、標準差與ANOVA分析結果
Table 2. Means and standard deviations of the total costs obtained by the four algorithms
n m CCGA CCGAII TGA GADR ANOVA(α = 0. 05) Avg. Std. Avg. Std. Avg. Std. Avg. Std. F P-value 20 2 2.80 3.37 3.74 4.36 7.54 5.38 14.88 18.22 15.40 4.88×10-9 5 1.28 2.15 1.76 2.83 3.44 3.33 9.44 13.86 13.07 8.15×10－8 50 2 3.90 4.22 9.84 7.80 35.02 12.17 59.06 53.86 40.93 1.39×10-20 5 1.36 2.61 4.60 5.71 23.00 10.90 17.82 19.68 39.41 5.63×10-20 10 1.46 2.60 3.78 4.39 18.60 8.71 7.22 8.43 66.85 8.15×10-30 100 2 9.36 5.99 29.04 10.16 97.54 16.84 275.28 137.86 150.81 1.13×10-50 5 6.38 5.81 19.98 11.15 77.04 15.05 72.12 55.02 75.72 1.44×10-32 10 2.28 2.98 10.16 8.34 62.40 15.30 34.54 32.61 106.78 5.25×10-41 15 1.46 2.14 7.04 6.71 55.66 13.32 24.68 27.25 122.77 8.93×10-45 20 1.14 1.96 6.02 6.47 54.40 11.68 12.74 14.25 307.94 6.80×10-74 150 2 19.76 10.20 57.96 16.16 154.78 19.06 606.68 236.72 258.03 8.62×10-68 5 9.30 7.13 37.68 15.44 122.58 20.62 165.22 89.23 121.48 1.75×10-44 10 5.20 4.94 23.54 12.99 107.70 20.60 72.60 47.45 151.68 7.59×10-51 15 4.78 5.49 20.46 11.34 105.52 16.39 62.42 48.72 149.19 9.29×10-50 20 4.40 4.82 13.86 8.80 100.98 16.69 48.60 39.99 193.02 2.97×10-58 200 2 34.32 12.87 107.68 24.49 224.46 26.05 1217.00 436.96 317.92 5.14×10-75 5 19.48 10.40 69.84 20.07 175.78 22.11 343.62 135.49 212.14 2.75×10-61 10 12.42 6.76 45.28 18.15 151.48 19.03 150.94 76.30 157.65 5.35×10-52 15 10.14 5.57 38.70 14.85 150.72 19.74 121.56 77.5 133.52 3.90×10-47 20 4.78 4.48 23.82 10.77 135.92 20.03 77.06 46.06 261.06 3.45×10-68 平均值 7.80 5.32 26.74 11.05 93.23 15.65 169.67 80.77 218.11 4.9×10-131
下載: 導出CSV
表 3 4種算法生成零成本問題解的算例數量
Table 3. Number of solutions with zero total cost produced by the four algorithms
n m CCGA CCGAII TGA GADR n m CCGA CCGAII TGA GADR 20 2 20 19 3 17 150 2 0 0 0 0 5 31 28 14 21 5 2 0 0 0 50 2 14 7 0 1 10 8 0 0 1 5 31 23 0 13 15 9 0 0 2 10 33 20 1 22 20 12 0 0 3 100 2 0 0 0 0 200 2 0 0 0 0 5 7 0 0 1 5 0 0 0 0 10 22 7 0 5 10 0 0 0 0 15 24 11 0 12 15 1 0 0 0 20 32 11 0 15 20 9 0 0 0 總計 255 126 18 113
下載: 導出CSV
中文字幕在线观看表 4 4種算法的CPU時間
Table 4. CPU times of the four algorithms?
s n m CCGA CCGAII TGA GADR n m CCGA CCGAII TGA GADR 20 5 0.31 0.30 0.59 0.84 200 20 33.91 32.41 66.45 241.31 100 10 7.72 7.37 15.46 32.98 平均值 14.24 13.23 23.28 72.28
下載: 導出CSV
-
參考文獻
[1] Slotnick S A. Order acceptance and scheduling: a taxonomy and review. Eur J Oper Res, 2011, 212(1): 1 doi: 10.1016/j.ejor.2010.09.042 [2] Shabtay D, Gaspar N, Kaspi M. A survey on offline scheduling with rejection. J Scheduling, 2013, 16(1): 3 doi: 10.1007/s10951-012-0303-z [3] Angel E, Bampis E, Kononov A.A FPTAS for approximating the unrelated parallel machines scheduling problem with costs//European Symposium on Algorithms.Berlin, 2001: 194 [4] Hoogeveen H, Skutella M, Woeginger G J. Preemptive scheduling with rejection. Math Program, 2003, 94(2-3): 361 doi: 10.1007/s10107-002-0324-z [5] Sengupta S.Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection//International Workshop on Algorithms and Data Structures.Ottawa, 2003: 79 [6] Miao C X, Zhang Y Z, Wang C F.Bounded parallel-batch scheduling on unrelated parallel machines//International Conference on Algorithmic Applications in Management.Berlin, 2010: 220 [7] Hsu C J, Chang C W. Unrelated parallel-machine scheduling with deteriorating jobs and rejection. Appl Mech Mater, 2012, 263- 266: 655 doi: 10.4028/www.scientific.net/AMM.263-266.655 [8] Lin F, Zhang X Z, Cai Z X. Approximation algorithms for scheduling with rejection on two unrelated parallel machines. Int J Adv Comput Sci Appl, 2015, 6(11): 260 https://journals.indexcopernicus.com/search/article?icid=1185391 [9] Jiang D K, Tan J Y. Scheduling with job rejection and nonsimultaneous machine available time on unrelated parallel machines. Theor Comput Sci, 2016, 616: 94 doi: 10.1016/j.tcs.2015.12.020 [10] Joo C M, Kim B S. Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability. Comput Ind Eng, 2015, 85: 102 doi: 10.1016/j.cie.2015.02.029 [11] Chen J S, Yang J S. Model formulations for the machine scheduling problem with limited waiting time constraints. J Inform Optimiz Sci, 2006, 27(1): 225 doi: 10.1080/02522667.2006.10699688 [12] Vallada E, Ruiz R. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. Eur J Oper Res, 2011, 211(3): 612 doi: 10.1016/j.ejor.2011.01.011 [13] Wu K J, Lu H W. PCEGA used to solve text feature selection. Syst Eng Theory Pract, 2012, 32(10): 2215 https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201210014.htm鄔開俊, 魯懷偉. 采用并行協同進化遺傳算法的文本特征選擇. 系統工程理論與實踐, 2012, 32(10): 2215 https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201210014.htm [14] Li X D, Yao X. Cooperatively coevolving particle swarms for large scale optimization. IEEE Trans Evol Comput, 2012, 16 (2): 210 doi: 10.1109/TEVC.2011.2112662 [15] Pan Q K. An effective co-evolutionary artificial bee colony algorithm for steelmaking- continuous casting scheduling. Eur J Oper Res, 2016, 250(3): 702 doi: 10.1016/j.ejor.2015.10.007 [16] Li M J, Tong T S. A partheno genetic algorithm and analysis on its global convergence. Acta Autom Sin, 1999, 25(1): 68 https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO901.009.htm(李茂軍, 童調生. 單親遺傳算法及其全局收斂性分析. 自動化學報, 1999, 25(1): 68) https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO901.009.htm [17] Wang J L, Huang W B, Ma G W, et al. An improved partheno genetic algorithm for multi-objective economic dispatch in cascaded hydropower systems. Int J Electr Power Energy Syst, 2015, 67: 591 doi: 10.1016/j.ijepes.2014.12.037 [18] Zhu X, Li X P. Iterative search method for total flowtime minimization no-wait flowshop problem. Int J Mach Learn Cybern, 2015, 6(5): 747 doi: 10.1007/s13042-014-0312-7 [19] Chen C L, Tzeng Y R, Chen C L. A new heuristic based on local best solution for permutation flow shop scheduling. Appl Soft Comput, 2015, 29: 75 doi: 10.1016/j.asoc.2014.12.011 -
點擊查看大圖
圖(4) / 表(4)
計量
- 文章訪問數: 1086
- HTML全文瀏覽量: 483
- PDF下載量: 26
- 被引次數: 0
