Optimization of aircraft moving assembly line scheduling problem considering material delivery
-
摘要:
以飞机移动生产线为实际背景,将作业装配过程调度抽象为资源受限项目调度问题并进行了扩展,引入物料配送与线边存储决策,以及相关能力约束等实际因素,建立了以装配总工期最小化为目标的数学模型。针对模型,设计了一种以遗传算法为框架的启发式算法,其中结合了解生成算法和局部优化搜索算法。在遗传算法较优的全局搜索能力下,通过SCRDS算法综合作业顺序、资源约束、配送能力、线边空间等因素,联合决策作业开始时间、物料配送时间和物料在线边空间的存储位置,提出了两作业间物料摆放位置调整的局部优化搜索算法,对作业开始时间和物料配送时间进行再优化,进一步缩短了装配总工期。利用标准算例库进行了数值实验,实验结果证明了模型与算法的有效性。
Abstract:This paper abstracted the scheduling of assembly process as a resource-constrained project scheduling problem in the background of aircraft moving assembly line, and decisions about material delivery and the storage of line-side material were introduced considering the capabilities, constraints and other practical factors. An integrating mathematical model with the objective of minimizing the makespan was established. A heuristic algorithm was proposed based on genetic algorithm framework, combining with solution generation algorithm and local optimization search algorithm. With the global searching advantages of genetic algorithm, a joint decision of start time, material delivery time and material storage position in line-side space for each job was made taking into account job sequence, resource constraints, delivery capability, line-side space and other factors through SCRDS algorithm. On this basis, a local optimization algorithm aiming at adjusting line-side material positions between two jobs was proposed to re-optimize the start time and material delivery time of jobs, which decreases the project duration further. Numerical experiments were carried out by using a standard example library and the results proved the validity of the model and algorithm.
-
表 1 小规模算例数值实验结果
Table 1. Numerical experiment results of small-scale examples
作业规模 算例 Dur/TCPU GAP/% CPLEX THBG 10 1 16/0.58 16/0.54 0.00 2 23/1.43 23/0.53 0.00 3 13/1.61 13/0.53 0.00 4 34/2.77 34/0.52 0.00 5 20/1.11 20/0.50 0.00 6 31/0.93 31/0.54 0.00 7 20/0.92 20/0.52 0.00 8 22/1.87 22/0.52 0.00 9 22/0.58 22/0.49 0.00 10 20/1.05 20/0.51 0.00 平均值 22.1/1.29 22.1/0.52 0.00 20 1 24/66.67 24/0.83 0.00 2 24/6.14 24/0.83 0.00 3 33/126.88 35/0.83 5.71 4 36/23.06 36/0.84 0.00 5 24/13.29 24/0.83 0.00 6 18/3.63 18/0.85 0.00 7 24/21.36 24/0.84 0.00 8 27/7.28 27/0.82 0.00 9 22/3.58 22/0.83 0.00 10 22/17.50 23/0.85 4.35 平均值 25.4/28.94 25.7/0.84 1.01 30 1 43/810 43/1.52 0.00 2 53/677 53/1.54 0.00 3 37/3 478 37/1.46 0.00 4 41/9 478 42/1.58 2.44 5 46/25 007 47/1.49 2.17 6 42/3 811 42/1.71 0.00 7 61/14 967 62/1.48 1.64 8 LB=52/- 57/1.47 9.62* 9 LB=51/- 57/1.48 11.76* 10 61/32 927 61/1.50 0.00 平均值 48/11 394 50.1/1.52 0.78 注:CPLEX栏中数据,如16/0.58表示CPLEX求得的精确解和CPU时间,LB=52/-表示CPLEX在可接受时间(36 000 s)内无法求出问题可行解,记录其低界值LB=52;THBG栏中数据,如16/0.54表示THBG算法得到的解和CPU时间;GAP栏中“*”表示CPLEX得不到可行解时用低界计算GAP值。 表 2 不同算法工期结果和优化比例
Table 2. Durations and optimal proportion of different algorithms
作业规模 Dur GAP/% R-NMO H-TD H-SCRDS THBG R-NMO H-TD H-SCRDS 30 54.86 56.24 50.17 50.10 9.79 12.38 0.14 60 74.70 73.45 61.89 61.40 21.81 19.19 0.80 90 91.70 93.65 76.03 75.00 22.80 23.78 1.37 120 137.30 156.05 111.53 108.90 26.48 41.75 2.42 480 395.48 393.37 305.24 296.37 33.44 32.73 2.99 1 200 981.50 1 033.62 739.00 709.44 38.35 45.70 4.17 -
[1] CHALESHTARTI A S, SHADROKH S. Branch and bound algorithms for resource constrained project scheduling problem subject to cumulative resources[C]//International Conference on Information Management, Innovation Management and Industrial Engineering.Piscataway, NJ:IEEE Press, 2011:147-152. [2] BERTHOLD T, HEINZ S, LVBBECKE M E, et al.A constraint integer programming approach for resource-constrained project scheduling[M]//LODI A, MILANO M, TOTH P.Integration of AI and OR techniques in constraint programming for combinatorial optimization problems.Berlin:Springer, 2010:313-317. [3] BLAZEWICZ J, LENSTRA J K, KAN A H G R.Scheduling subject to resource constraints:Classification and complexity[J].Discrete Applied Mathematics, 1983, 5(1):11-24. doi: 10.1016/0166-218X(83)90012-4 [4] TORMOS P, LOVA A.An efficient multi-pass heuristic for project scheduling with constrained resources[J].International Journal of Production Research, 2003, 41(5):1071-1086. doi: 10.1080/0020754021000033904 [5] BUKATA L, ŠǓCHA P, HANZÁLEK Z.Solving the resource constrained project scheduling problem using the parallel Tabu search designed for the CUDA platform[J].Journal of Parallel & Distributed Computing, 2014, 77(11):58-68. http://www.sciencedirect.com/science/article/pii/S0743731514002226 [6] BOULEIMEN K, LECOCQ H.A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version[J].European Journal of Operational Research, 2003, 149(2):268-281. doi: 10.1016/S0377-2217(02)00761-0 [7] ALCARAZ J, MAROTO C.A robust genetic algorithm for resource allocation in project scheduling[J].Annals of Operations Research, 2013, 102(1):83-109. doi: 10.1023/A:1010949931021 [8] HARTMANN S.A self-adapting genetic algorithm for project scheduling under resource constraints[J].Naval Research Logistics, 2002, 49(5):433-448. doi: 10.1002/(ISSN)1520-6750 [9] MERKLE D, MIDDENDORF M, SCHMECK H.Ant colony optimization for resource-constrained project scheduling[J].IEEE Transactions on Evolutionary Computation, 2002, 6(4):333-346. doi: 10.1109/TEVC.2002.802450 [10] KUMAR N, VIDYARTHI D P.A model for resource-constrained project scheduling using adaptive PSO[J].Soft Computing, 2015, 20(4):1565-1580. doi: 10.1007/s00500-015-1606-8.pdf [11] 王琰, 陆志强.基于多重约束的飞机移动装配线作业调度优化[J].工业工程与管理, 2011, 16(6):115-120. http://www.wenkuxiazai.com/doc/b613ef250066f5335a8121d0.htmlWANG Y, LU Z Q.Job scheduling optimization of aircraft moving assembly line under multiple constraints[J].Industrial Engineering & Management, 2011, 16(6):115-120(in Chinese). http://www.wenkuxiazai.com/doc/b613ef250066f5335a8121d0.html [12] 郑倩, 奚立峰.飞机移动生产线作业调度问题的启发式算法[J].工业工程与管理, 2015, 20(2):116-121. http://www.cnki.com.cn/Article/CJFDTotal-GYGC201502018.htmZHENG Q, XI L F.Heuristics for aircraft moving assembly line scheduling problem[J].Industrial Engineering & Management, 2015, 20(2):116-121(in Chinese). http://www.cnki.com.cn/Article/CJFDTotal-GYGC201502018.htm [13] 葛茂根, 刘明周, 钱芳, 等.基于JIT的多目标总装准时物料配送方法研究[J].中国机械工程, 2011, 22(23):2834-2838. http://www.docin.com/p-516302403.htmlGE M G, LIU M Z, QIAN F, et al.Research on multi-objective method on main assembly material delivery based on JIT[J].China Mechanical Engineering, 2011, 22(23):2834-2838(in Chinese). http://www.docin.com/p-516302403.html [14] FATHI M, ALVAREZ M J, MEHRABAN F H, et al.A multiobjective optimization algorithm to solve the part feeding problem in mixed-model assembly lines[J].Mathematical Problems in Engineering, 2014, 11(1):809-812. http://connection.ebscohost.com/c/articles/100526854/multiobjective-optimization-algorithm-solve-part-feeding-problem-mixed-model-assembly-lines [15] FATHI M, RODRÍGUEZ V, FONTES D B M M, et al.A modified particle swarm optimization algorithm to solve the part feeding problem at assembly lines[J].International Journal of Production Research, 2016, 54(3):1-16. doi: 10.1080/00207543.2015.1090032?journalCode=tprs20 [16] KHAYAT G E, LANGEVIN A, RIOPEL D.Integrated production and material handling scheduling using mathematical programming and constraint programming[J].European Journal of Operational Research, 2006, 175(3):1818-1832. doi: 10.1016/j.ejor.2005.02.077 [17] AGUIRRE A M, MÉNDEZ C A, CASTRO P M.A hybrid scheduling approach for automated flowshops with material handling and time constraints[J].International Journal of Production Research, 2014, 52(9):2788-2806. doi: 10.1080/00207543.2014.885664