服务水平约束下的成套订单排序研究
|
摘要
面对具有不同加工要求和不同完工期限的客户定制产品，如何进行合理的生产作业计划安排和调度，以较低的生产成本最大限度地满足顾客的要求，一直是生产运作理论界关心的问题。本学位论文对并行机环境下具有服务水平约束的成套订单多目标优化问题做了一些基础性的研究。
论文首先介绍了成套订单问题的定义、成套订单的排序问题，以此作为全文研究的出发点和基础。接着论文在上述问题的基础上进行拓展，对不含调整时间的并行机加工条件下的成套订单问题进行了研究。以三台并行机的加工过程为基础，以最大化加权成套率和最小化最大完工时间为双重目标,建立该问题的多目标规划模型，提出修复启发算法与遗传算法相结合的混合遗传算法来求解该模型，并通过一个算例对该类排序问题和所提出的算法进行说明，实验结果显示采用模函数或商函数的混合遗传算法均具有很强的寻优功能，但模函数法比商函数法更适合作为本算法的适应度函数。然后，论文在上述研究的基础上进一步拓展，增加考虑了加工工件具有多种类型和不同类型加工需要机器调整时间的情况，以最大化加权成套率和最小化最大完工时间为双重目标，建立了此种情况下的多目标规划模型，在修复启发算法、基于全排列的机器分配法、Pareto支配关系、精英保留机制与小生境淘汰法的基础上，设计出了针对该问题的非支配排序混合遗传算法，并通过数据模拟验证了该算法的广适应性、强有效性和快收敛性。
With different processing requirements and the due time limits of customized ordersor customized jobs, how to schedule the production of jobs to ma ximize the dema nd ofcustomer is always being the hot problem in the research field of production operation . Inthis thesis, we select parallel machines operation as the research background and discusshow to scheduling the production of the whole set orders with service level to ma ximizethe weighted whole set rate and minimize the completion time. Also we propose twomulti-objective models and algorithms to solve the problem of our research.
First, a definition of the whole set orders problem is introduced as the base of thewhole research. On the basis of the basic scheduling research of whole set orders problem,considered the process of parallel machines without setup time of whole set orders and itscomplexity. On the condition of three parallel machines, with the objects to ma ximize theweighted whole set rate and minimize the completion time, we establish a multi-objectiveprogramming model. In addition, a hybrid algorithm combined of genetic algorithm andthe RP heuristic algorithm is designed to solve the above model. An example is given toprove the efficiency of the hybrid algorithm, but matrix function is more fitted to thisproblem than quotient function. And then, considered the process of parallel machines withsetup time of whole set orders, we propose another multi-objective model. With the guideof Pareto optima l solution, elitist preserve, niche approach, RP heuristic algorithm andmachine distribution method based of whole permutation, a non-domina ted ranking geneticalgorithm is designed to solve the above model. The result of the simulation experiment isgiven to prove the wide adaptability, the strong valid ity and the fast convergence of thealgorithm.
论文首先介绍了成套订单问题的定义、成套订单的排序问题，以此作为全文研究的出发点和基础。接着论文在上述问题的基础上进行拓展，对不含调整时间的并行机加工条件下的成套订单问题进行了研究。以三台并行机的加工过程为基础，以最大化加权成套率和最小化最大完工时间为双重目标,建立该问题的多目标规划模型，提出修复启发算法与遗传算法相结合的混合遗传算法来求解该模型，并通过一个算例对该类排序问题和所提出的算法进行说明，实验结果显示采用模函数或商函数的混合遗传算法均具有很强的寻优功能，但模函数法比商函数法更适合作为本算法的适应度函数。然后，论文在上述研究的基础上进一步拓展，增加考虑了加工工件具有多种类型和不同类型加工需要机器调整时间的情况，以最大化加权成套率和最小化最大完工时间为双重目标，建立了此种情况下的多目标规划模型，在修复启发算法、基于全排列的机器分配法、Pareto支配关系、精英保留机制与小生境淘汰法的基础上，设计出了针对该问题的非支配排序混合遗传算法，并通过数据模拟验证了该算法的广适应性、强有效性和快收敛性。
With different processing requirements and the due time limits of customized ordersor customized jobs, how to schedule the production of jobs to ma ximize the dema nd ofcustomer is always being the hot problem in the research field of production operation . Inthis thesis, we select parallel machines operation as the research background and discusshow to scheduling the production of the whole set orders with service level to ma ximizethe weighted whole set rate and minimize the completion time. Also we propose twomulti-objective models and algorithms to solve the problem of our research.
First, a definition of the whole set orders problem is introduced as the base of thewhole research. On the basis of the basic scheduling research of whole set orders problem,considered the process of parallel machines without setup time of whole set orders and itscomplexity. On the condition of three parallel machines, with the objects to ma ximize theweighted whole set rate and minimize the completion time, we establish a multi-objectiveprogramming model. In addition, a hybrid algorithm combined of genetic algorithm andthe RP heuristic algorithm is designed to solve the above model. An example is given toprove the efficiency of the hybrid algorithm, but matrix function is more fitted to thisproblem than quotient function. And then, considered the process of parallel machines withsetup time of whole set orders, we propose another multi-objective model. With the guideof Pareto optima l solution, elitist preserve, niche approach, RP heuristic algorithm andmachine distribution method based of whole permutation, a non-domina ted ranking geneticalgorithm is designed to solve the above model. The result of the simulation experiment isgiven to prove the wide adaptability, the strong valid ity and the fast convergence of thealgorithm.
引文
[1]唐恒永,赵传立.排序引论[M].北京:科学出版社,2002
[2] B. Chen, C.N. Potts and G.J. Woeginger. A review of machine scheduling:Complexity, algorithms and approximability[J]. Handbook of Combinatoria lOptimiza tion, 1998, 3: 21-169
[3]何军辉,周泓.求解含调整时间并行机排序问题的遗传算法[J].系统工程理论方法应用. 2002,11(4):285-289
[4]贺仁杰,谭跃进.具有时间窗口约束的并行机床调度问题研究[J].系统工程.2004,22(5):18-22
[5] Jatinder N.D., Gupta, Johnny C.Ho. Minimizing makespan subject to minimumflowtime on two identica l parallel machines[J]. Computer&Operations Research.2001, 28: 705-717
[6] Peihai Liu, Xiwen Lu. On-line scheduling of parallel machines to minimize totalcompletion times[J]. Computer&Operations Research. 2009, 36: 2647-2652
[7] Leah Epstein, Rob van stee. Optima l on-line time with resource augmentation[J].Discrete Applied Mathema tics. 2006,154(11):611-621
[8] Ming Liu, Yinfeng Xu, Chengbin Chu, Feifeng Zheng. Online scheduling on twouniform machines to minimize the makespan[J]. Theoretical Computer Science. 2009,410: 2099-2109
[9] Dehua Xu, Zhenmin Cheng, Yunqiang Yin, Hongxing Li. Makespan minimiza tion fortwo parallel machines scheduling with a period ic availability constraint[J]. Computer& Operations Research. 2009, 36: 1809-1812
[10] Kellerer H., Kotov,V., Speranza M.R., Tuza Z.. Semi on-line algorithms for thepartition problem[J]. Operations Research Letters. 1997, 21: 235-242
[11] He Y., Zha ng,G.. Semi on-line scheduling on two identica l machines[J]. Computing.1999, 62: 179-187
[12] Zhiyi Tan，Yong He. Semi-online scheduling problems on two identica l machines withinexact partial information[J]. Theoretical Computer Science. 2007, 377(4):110-125
[13] M. Ghirardi, C. N. Potts. Makespan minimiza tion for scheduling unrelated parallelmachines: A recovering beam search approach[J]. European Journal of Operationa lRearch. 2005, 165: 457-467
[14]张居阳,孙吉贵,杨轻云.半在线调度中约束求解算法研究[J].自动化学报.2007,33(7):765-767
[15]刘民,吴澄,蒋新松.用遗传算法解决并行多机调度问题[J].系统工程理论和实践.1998,18(1):14-17
[16]曹江北,陈义保.相同并行机上工件排序问题的一种新算法[J].系统工程理论方法应用. 2003,12(4):363-366
[17]衣杨,汪定伟.并行多机成组工作总流水时间调度问题[J].计算机集成制造系统.2001,7(7):7-11
[18] Vinicius Amara l Armentano, Moacir Felizardo de Franca Filho. Minimizing totaltardiness in parallel machine scheduling with setup times: An adaptive memory-basedGRASP approach[J]. European Journal of Operationa l Research. 2007, 183: 100-114
[19] Emma nuel Neron, Fabrice Tercinet, Francis Sourd. Search tree based approaches forparallel machine scheduling[J]. Computers and Operations. 2008, 35: 1127-1137
[20] Min Ji, T.C.E. Cheng. Parallel-machine scheduling with simple linear deterioration tominimize total completion time[J]. European Journal of Operationa l Research. 2008,118(14):342-347
[21]周水银,盛培峰.面向成套订单问题的工艺规划与排序的集成研究[J].中国管理科学.2006,14(5):73-80
[22]周水银,陈荣秋.单机加权成套订单数遗传算法研究[J].系统工程.2005,23(5):22-24
[23]周水银,王玮.不确定性环境下的单机成套订单鲁棒计划[J].工业工程与管理.2008,6:32-35
[24]吴春辉,周水银.并行多机加权成套订单数极大化的混合遗传算法[J].系统工程理论与实践.2006,26(11):125-129
[25]苏亚,傅青.并行机含调整时间成套订单数问题遗传算法[J].控制工程.2007,14(1):78-81
[26]周水银,傅青.最大化流水作业加权成套订单数的研究[J].控制工程.2007,14(2):212-214
[27]傅青,周水银.面向成套订单的生产与配送协调的排序研究[J].工业工程与管理.2008,(5):21-28
[28]唐国春.误工排序问题的赶工分析[J].上海第二工业大学学报. 1994,(2):1-6
[29]彭敏,杨丽,许保光.单资源调度中误工问题的作业时间压缩算法[J].中国管理科学.2008.13(4):44-50
[30] Foulds,L. Tang Guochun. A Crash Analysis of Scheduling to Minimize the Number oflate jobs[J]. Asia-Pacific Journal of Operationa l Research. 1995, 12(1): 5-15
[31] Zhaohui Liu, Wen Yu. Minimizing the Number of Late Jobs Under the GroupTechnology[J]. Assumption.JCO.1999, 3(2): 5-15
[32] Jeffrey Schaller. Scheduling on a single machine with family setups to minimize totaltardiness[J]. Int. J. Production Economics. 2007, 105: 329-344
[33] Fariborz Jola i. Minimizing number of tardy jobs on a batch processing machine withincompatible job families[J]. 2005, 162: 184-190
[34] L. L. Liu, C. T. Ng, T. C. E. Cheng. Scheduling jobs with release dates on parallelbatch processing machines[J]. Discrete Applied Mathema tics. 2009, 157: 1825-1830
[35]严培胜,高成修.带可分配工期的总误工问题的应急管理[J].数学杂志.2008,28(4):462-468
[36]郑金华.多目标进化算法及其应用[M].北京:科学出版社,2007
[37] Coello Coello Carlos A.,etc.. Evolutiona ry Algortithms for Solving Multi-Objectiveproblems. Kluwer Acedemic/Plenum Publishers, 2002
[38] D. Schaffer. Multiple objective optimization with vector evaluated geneticalgorithms[C]. Proceedings of the First Internationa l Conference on GeneticAlgorithms, Lawrence Erlbaum. 1985: 93-100
[39] F. Kurasawe. A varia nt of evolution strategies for vector optimization[C]. In ParallelProblem Solving from Nature, Lecture Notes in Computer Science, Berlin. 1991:193–197
[40] P. Serafini. Simula ted Annealing for Multiple Objective Optimiza tion Problems[C].Proceedings of the Tenth Internationa l Conference on Multiple Criteria DecisionMaking, Taipei. 1992, 1:87–96
[41] M. P. Hansen. Tabu Search for Multi objective Optimiza tion: MOTS[C]. Technica lReport Presented at 13th Internationa l Conference on MCDM, Denmark, 1997
[42] J. Ulungu, P. H. Teghem, D. Fortemps etc.. MOSA Method: A Tool for Solving Multiobjective Combinatoria l Optimiza tion Problems[J]. Journal of Multi Criteria DecisionAnalysis. 1999, 8: 221-236.
[43] C. M. Fonesca, P. J. Fleming. Genetic algorithms for multi objective optimization:Formula tion, discussion and genera lization[C]. Proceedings of the 5th Internationa lConference on Genetic Algorithms, San Mateo,California,1993: 416-423
[44] J. Horn, N. Nafpliotis, D.E.Goldberg. A Niched Pareto Genetic Algorithm for Multiobjective Optimiza tion[C]. Proceedings of the First IEEE Conference onEvolutiona ry Computation, Piscataway USA,1994:82-87
[45] N. Srinivas and K. Deb. Multi-objective optimization using non-domina ted sorting ingenetic algorithms[J]. Evolutiona ry Computation. 1994, 2(3):221–248
[46] E. Zitzler, L. Thiele. Multi objective Evolutiona ry Algorithms: A Comparative CaseStudy and the Strength Pareto Approach[J]. IEEE Transactions on Evolutiona ryComputation. 1999, 3(4):257-271
[47] E. Zitzler, M. Laumanns, L.Thiele. SPEA2: Improving the strength paretoevolutionary algorithm[J]. TIK-Report 103. 2001
[48] K. Deb, A. Pratap, S. Agarwal etc.. A fast and elitist multi-objective genetic algorithmNSGA-II[J]. IEEE Transaction on Evolutiona ry Computation. 2002, l6(2):182-197
[49] J. D. Knowles, D. W. Corne. The Pareto archived evolution strategy: a new baselinealgorithm for multi objective optimization[J]. In 1999 Congress on Evolutiona ryComputation, Piscataway, NJ. 1999: 98-105
[50] J. D. Knowles, D. W. Corne. M-PAES:A Meme tic Algorithm for Multi objectiveOptimiza tion[C]. Proceedings of the 2000 Congress on Evolutiona ry Computation,Piscataway, NJ. 2000, 1:325-332
[51] C. A. C. Coello, G.T. Pulido, and M. S. Lechuga. Handling multiple objectives withparticle swarm optimization[J]. IEEE Transaction on Evolutiona ry Computation.2004, 8(3):256–279.
[52] George Steiner, Paul Stephenson. Pareto optima for total weighted completion timeand ma ximum lateness on a single machine[J]. Discrete Applied Mathema tics,2007,155(11): 2341-2354
[53]柴玉梅,张靖.一种新的多目标优化策略机制及其应用[J].计算机应用.2007,27(9):2287-2289
[54]李春华,朱新坚,曹广益.基于人工免疫系统的多目标函数优化[J].计算机工程与应用. 2008,44(1):28-30
[55] Ozgun Baris, Bekki, Meral Azizoglu. Operationa l fixed interval scheduling problemon uniform parallel machines[J]. Production Economics. 2008, 112: 756-768
[2] B. Chen, C.N. Potts and G.J. Woeginger. A review of machine scheduling:Complexity, algorithms and approximability[J]. Handbook of Combinatoria lOptimiza tion, 1998, 3: 21-169
[3]何军辉,周泓.求解含调整时间并行机排序问题的遗传算法[J].系统工程理论方法应用. 2002,11(4):285-289
[4]贺仁杰,谭跃进.具有时间窗口约束的并行机床调度问题研究[J].系统工程.2004,22(5):18-22
[5] Jatinder N.D., Gupta, Johnny C.Ho. Minimizing makespan subject to minimumflowtime on two identica l parallel machines[J]. Computer&Operations Research.2001, 28: 705-717
[6] Peihai Liu, Xiwen Lu. On-line scheduling of parallel machines to minimize totalcompletion times[J]. Computer&Operations Research. 2009, 36: 2647-2652
[7] Leah Epstein, Rob van stee. Optima l on-line time with resource augmentation[J].Discrete Applied Mathema tics. 2006,154(11):611-621
[8] Ming Liu, Yinfeng Xu, Chengbin Chu, Feifeng Zheng. Online scheduling on twouniform machines to minimize the makespan[J]. Theoretical Computer Science. 2009,410: 2099-2109
[9] Dehua Xu, Zhenmin Cheng, Yunqiang Yin, Hongxing Li. Makespan minimiza tion fortwo parallel machines scheduling with a period ic availability constraint[J]. Computer& Operations Research. 2009, 36: 1809-1812
[10] Kellerer H., Kotov,V., Speranza M.R., Tuza Z.. Semi on-line algorithms for thepartition problem[J]. Operations Research Letters. 1997, 21: 235-242
[11] He Y., Zha ng,G.. Semi on-line scheduling on two identica l machines[J]. Computing.1999, 62: 179-187
[12] Zhiyi Tan，Yong He. Semi-online scheduling problems on two identica l machines withinexact partial information[J]. Theoretical Computer Science. 2007, 377(4):110-125
[13] M. Ghirardi, C. N. Potts. Makespan minimiza tion for scheduling unrelated parallelmachines: A recovering beam search approach[J]. European Journal of Operationa lRearch. 2005, 165: 457-467
[14]张居阳,孙吉贵,杨轻云.半在线调度中约束求解算法研究[J].自动化学报.2007,33(7):765-767
[15]刘民,吴澄,蒋新松.用遗传算法解决并行多机调度问题[J].系统工程理论和实践.1998,18(1):14-17
[16]曹江北,陈义保.相同并行机上工件排序问题的一种新算法[J].系统工程理论方法应用. 2003,12(4):363-366
[17]衣杨,汪定伟.并行多机成组工作总流水时间调度问题[J].计算机集成制造系统.2001,7(7):7-11
[18] Vinicius Amara l Armentano, Moacir Felizardo de Franca Filho. Minimizing totaltardiness in parallel machine scheduling with setup times: An adaptive memory-basedGRASP approach[J]. European Journal of Operationa l Research. 2007, 183: 100-114
[19] Emma nuel Neron, Fabrice Tercinet, Francis Sourd. Search tree based approaches forparallel machine scheduling[J]. Computers and Operations. 2008, 35: 1127-1137
[20] Min Ji, T.C.E. Cheng. Parallel-machine scheduling with simple linear deterioration tominimize total completion time[J]. European Journal of Operationa l Research. 2008,118(14):342-347
[21]周水银,盛培峰.面向成套订单问题的工艺规划与排序的集成研究[J].中国管理科学.2006,14(5):73-80
[22]周水银,陈荣秋.单机加权成套订单数遗传算法研究[J].系统工程.2005,23(5):22-24
[23]周水银,王玮.不确定性环境下的单机成套订单鲁棒计划[J].工业工程与管理.2008,6:32-35
[24]吴春辉,周水银.并行多机加权成套订单数极大化的混合遗传算法[J].系统工程理论与实践.2006,26(11):125-129
[25]苏亚,傅青.并行机含调整时间成套订单数问题遗传算法[J].控制工程.2007,14(1):78-81
[26]周水银,傅青.最大化流水作业加权成套订单数的研究[J].控制工程.2007,14(2):212-214
[27]傅青,周水银.面向成套订单的生产与配送协调的排序研究[J].工业工程与管理.2008,(5):21-28
[28]唐国春.误工排序问题的赶工分析[J].上海第二工业大学学报. 1994,(2):1-6
[29]彭敏,杨丽,许保光.单资源调度中误工问题的作业时间压缩算法[J].中国管理科学.2008.13(4):44-50
[30] Foulds,L. Tang Guochun. A Crash Analysis of Scheduling to Minimize the Number oflate jobs[J]. Asia-Pacific Journal of Operationa l Research. 1995, 12(1): 5-15
[31] Zhaohui Liu, Wen Yu. Minimizing the Number of Late Jobs Under the GroupTechnology[J]. Assumption.JCO.1999, 3(2): 5-15
[32] Jeffrey Schaller. Scheduling on a single machine with family setups to minimize totaltardiness[J]. Int. J. Production Economics. 2007, 105: 329-344
[33] Fariborz Jola i. Minimizing number of tardy jobs on a batch processing machine withincompatible job families[J]. 2005, 162: 184-190
[34] L. L. Liu, C. T. Ng, T. C. E. Cheng. Scheduling jobs with release dates on parallelbatch processing machines[J]. Discrete Applied Mathema tics. 2009, 157: 1825-1830
[35]严培胜,高成修.带可分配工期的总误工问题的应急管理[J].数学杂志.2008,28(4):462-468
[36]郑金华.多目标进化算法及其应用[M].北京:科学出版社,2007
[37] Coello Coello Carlos A.,etc.. Evolutiona ry Algortithms for Solving Multi-Objectiveproblems. Kluwer Acedemic/Plenum Publishers, 2002
[38] D. Schaffer. Multiple objective optimization with vector evaluated geneticalgorithms[C]. Proceedings of the First Internationa l Conference on GeneticAlgorithms, Lawrence Erlbaum. 1985: 93-100
[39] F. Kurasawe. A varia nt of evolution strategies for vector optimization[C]. In ParallelProblem Solving from Nature, Lecture Notes in Computer Science, Berlin. 1991:193–197
[40] P. Serafini. Simula ted Annealing for Multiple Objective Optimiza tion Problems[C].Proceedings of the Tenth Internationa l Conference on Multiple Criteria DecisionMaking, Taipei. 1992, 1:87–96
[41] M. P. Hansen. Tabu Search for Multi objective Optimiza tion: MOTS[C]. Technica lReport Presented at 13th Internationa l Conference on MCDM, Denmark, 1997
[42] J. Ulungu, P. H. Teghem, D. Fortemps etc.. MOSA Method: A Tool for Solving Multiobjective Combinatoria l Optimiza tion Problems[J]. Journal of Multi Criteria DecisionAnalysis. 1999, 8: 221-236.
[43] C. M. Fonesca, P. J. Fleming. Genetic algorithms for multi objective optimization:Formula tion, discussion and genera lization[C]. Proceedings of the 5th Internationa lConference on Genetic Algorithms, San Mateo,California,1993: 416-423
[44] J. Horn, N. Nafpliotis, D.E.Goldberg. A Niched Pareto Genetic Algorithm for Multiobjective Optimiza tion[C]. Proceedings of the First IEEE Conference onEvolutiona ry Computation, Piscataway USA,1994:82-87
[45] N. Srinivas and K. Deb. Multi-objective optimization using non-domina ted sorting ingenetic algorithms[J]. Evolutiona ry Computation. 1994, 2(3):221–248
[46] E. Zitzler, L. Thiele. Multi objective Evolutiona ry Algorithms: A Comparative CaseStudy and the Strength Pareto Approach[J]. IEEE Transactions on Evolutiona ryComputation. 1999, 3(4):257-271
[47] E. Zitzler, M. Laumanns, L.Thiele. SPEA2: Improving the strength paretoevolutionary algorithm[J]. TIK-Report 103. 2001
[48] K. Deb, A. Pratap, S. Agarwal etc.. A fast and elitist multi-objective genetic algorithmNSGA-II[J]. IEEE Transaction on Evolutiona ry Computation. 2002, l6(2):182-197
[49] J. D. Knowles, D. W. Corne. The Pareto archived evolution strategy: a new baselinealgorithm for multi objective optimization[J]. In 1999 Congress on Evolutiona ryComputation, Piscataway, NJ. 1999: 98-105
[50] J. D. Knowles, D. W. Corne. M-PAES:A Meme tic Algorithm for Multi objectiveOptimiza tion[C]. Proceedings of the 2000 Congress on Evolutiona ry Computation,Piscataway, NJ. 2000, 1:325-332
[51] C. A. C. Coello, G.T. Pulido, and M. S. Lechuga. Handling multiple objectives withparticle swarm optimization[J]. IEEE Transaction on Evolutiona ry Computation.2004, 8(3):256–279.
[52] George Steiner, Paul Stephenson. Pareto optima for total weighted completion timeand ma ximum lateness on a single machine[J]. Discrete Applied Mathema tics,2007,155(11): 2341-2354
[53]柴玉梅,张靖.一种新的多目标优化策略机制及其应用[J].计算机应用.2007,27(9):2287-2289
[54]李春华,朱新坚,曹广益.基于人工免疫系统的多目标函数优化[J].计算机工程与应用. 2008,44(1):28-30
[55] Ozgun Baris, Bekki, Meral Azizoglu. Operationa l fixed interval scheduling problemon uniform parallel machines[J]. Production Economics. 2008, 112: 756-768