考虑资源转移时间的项目可拆分资源受限多项目调度问题
|
摘要
针对实际资源共享型节拍式流水装配生产过程中存在资源转移时间情况,提出考虑资源转移时间的的项目可拆分资源受限多项目调度问题,以最小化项目工期为目标建立了问题的数学模型。针对问题的特征,在现有算法的基础上,提出了双层循环迭代算法。项目拆分层考虑了资源转移时间对作业选取的影响,改进了作业选择的优先权值。项目调度层以自适应遗传算法为框架,分析资源转移时间对项目计划的影响,提出了基于局部两作业资源需求的并行调度机制。其中,新的调度机制考虑了不同情形下资源转移网络的构造方式。数据实验表明所提算法能够有效避免不合理的资源转移,在求解质量方面具有良好的性能。
For the practical situation where resource transfer time was inevitable in the process of specific product moving assembly line,the resource constrained project scheduling problem based on project splitting with resource transfer time was addressed,and a mathematical model with the objective of minimizing project makespan was established.Aiming at the problem's feature,an improved two-level iterative algorithm based on the recent research was developed.At the project splitting level,the priority value of activity chosen was improved by considering the effect of resource transfer time;at the project scheduling level,an improved parallel schedule generation scheme based on the resource requirement of two local activities was proposed to decode the chromosomes based on a self-adaption genetic algorithm.The improved parallel schedule generation scheme included the constructions of resource transfer network under different situation.Computational experiments revealed that the designed algorithm could avoid unreasonable resource transfer and improve the solution quality efficiently.
For the practical situation where resource transfer time was inevitable in the process of specific product moving assembly line,the resource constrained project scheduling problem based on project splitting with resource transfer time was addressed,and a mathematical model with the objective of minimizing project makespan was established.Aiming at the problem's feature,an improved two-level iterative algorithm based on the recent research was developed.At the project splitting level,the priority value of activity chosen was improved by considering the effect of resource transfer time;at the project scheduling level,an improved parallel schedule generation scheme based on the resource requirement of two local activities was proposed to decode the chromosomes based on a self-adaption genetic algorithm.The improved parallel schedule generation scheme included the constructions of resource transfer network under different situation.Computational experiments revealed that the designed algorithm could avoid unreasonable resource transfer and improve the solution quality efficiently.
引文
[1]LU Zhiqiang,YANG Chao.Modeling of resource constrained multi-project scheduling problem based on project splitting[J].Journal of Shanghai Jiao Tong University,2017,51(2):193-201(in Chinese).[陆志强,杨超.基于项目网络拆分决策的多项目协同调度问题建模[J].上海交通大学学报,2017,51(2):193-201.]
[2]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.
[3]KURTULUS I,DAVIS E W.Multi-project scheduling:categorization of heuristic rules performance[J].Management Science,1982,28(2):161-172.
[4]KURTULUS I S,NARULA S C.Multi-project scheduling:analysis of project performance[J].IIE Transactions,1985,17(1):58-66.
[5]TOFFOLO T A M,SANTOS H G,CARVALHO M A M,et al.An integer programming approach to the multimode resource-constrained multiproject scheduling problem[J].Journal of Scheduling,2016,19(3):295-307.
[6]CAN A,ULUSOY G.Multi-project scheduling with twostage decomposition[J].Annals of Operations Research,2014,217(1):95-116.
[7]WANG Junqiang,ZHANG Songfei,CHEN Jian,et al.Decomposition algorithm for resource-constrained multi-project scheduling problem[J].Computer Integrated Manufacturing Systems,2013,19(1):83-96(in Chinese).[王军强,张松飞,陈剑,等.一种求解资源受限多项目调度问题的分解算法[J].计算机集成制造系统,2013,19(1):83-96.]
[8]WANG Weixin,WANG Xu,GE Xianlong.Multi-mode and multi-project scheduling modeling and algorithm with activity splitting[J].Computer Integrated Manufacturing Systems,2014,20(6):1388-1397(in Chinese).[王伟鑫,王旭,葛显龙.任务可拆分的多模式多项目调度模型与算法[J].计算机集成制造系统,2014,20(6):1388-1397.]
[9]KRGER D.A heuristic solution framework for the resource constrained(multi-)project scheduling problem with sequencedependent transfer times[J].European Journal of Operational Research,2009,197(2):492-508.
[10]KRGER D.,SCHOLL A.Managing and modelling general resource transfers in(multi-)project scheduling[J].OR Spectrum,2010,32(2):369-394.
[11]ZONG Yan,LIU Qiong,ZHANG Chaoyong,et al.Multiproject scheduling problem with resource transfer time[J].Computer Integrated Manufacturing Systems,2011,17(9):1921-1928(in Chinese).[宗砚,刘琼,张超勇,等.考虑资源传递时间的多项目调度问题[J],计算机集成制造系统,2011,17(9):1921-1928.]
[12]WANG Wanliang,WU Qidi.Intelligent algorithm of production scheduling and its application[M].Beijing:Science Press,2007(in Chinese).[王万良,吴启迪.生产调度智能算法及其应用[M].北京:科学出版社,2007.]
[2]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.
[3]KURTULUS I,DAVIS E W.Multi-project scheduling:categorization of heuristic rules performance[J].Management Science,1982,28(2):161-172.
[4]KURTULUS I S,NARULA S C.Multi-project scheduling:analysis of project performance[J].IIE Transactions,1985,17(1):58-66.
[5]TOFFOLO T A M,SANTOS H G,CARVALHO M A M,et al.An integer programming approach to the multimode resource-constrained multiproject scheduling problem[J].Journal of Scheduling,2016,19(3):295-307.
[6]CAN A,ULUSOY G.Multi-project scheduling with twostage decomposition[J].Annals of Operations Research,2014,217(1):95-116.
[7]WANG Junqiang,ZHANG Songfei,CHEN Jian,et al.Decomposition algorithm for resource-constrained multi-project scheduling problem[J].Computer Integrated Manufacturing Systems,2013,19(1):83-96(in Chinese).[王军强,张松飞,陈剑,等.一种求解资源受限多项目调度问题的分解算法[J].计算机集成制造系统,2013,19(1):83-96.]
[8]WANG Weixin,WANG Xu,GE Xianlong.Multi-mode and multi-project scheduling modeling and algorithm with activity splitting[J].Computer Integrated Manufacturing Systems,2014,20(6):1388-1397(in Chinese).[王伟鑫,王旭,葛显龙.任务可拆分的多模式多项目调度模型与算法[J].计算机集成制造系统,2014,20(6):1388-1397.]
[9]KRGER D.A heuristic solution framework for the resource constrained(multi-)project scheduling problem with sequencedependent transfer times[J].European Journal of Operational Research,2009,197(2):492-508.
[10]KRGER D.,SCHOLL A.Managing and modelling general resource transfers in(multi-)project scheduling[J].OR Spectrum,2010,32(2):369-394.
[11]ZONG Yan,LIU Qiong,ZHANG Chaoyong,et al.Multiproject scheduling problem with resource transfer time[J].Computer Integrated Manufacturing Systems,2011,17(9):1921-1928(in Chinese).[宗砚,刘琼,张超勇,等.考虑资源传递时间的多项目调度问题[J],计算机集成制造系统,2011,17(9):1921-1928.]
[12]WANG Wanliang,WU Qidi.Intelligent algorithm of production scheduling and its application[M].Beijing:Science Press,2007(in Chinese).[王万良,吴启迪.生产调度智能算法及其应用[M].北京:科学出版社,2007.]