·538· 工程科学学报，第41卷，第4期 4]Hoogeveen H,Skutella M,Woeginger GJ.Preemptive scheduling with rejection.Math Program,2003,94(23):361 ]Sengupta S.Algorithms and approximation schemes for minimum CADR lateness/tardiness scheduling with rejection//International Work- shop on Algorithms and Data Structures.Ottawa,2003:79 CCGAII ] Miao C X,Zhang Y Z,Wang C F.Bounded parallel-batch sched- CCCA uling on unrelated parallel machines/International Conference on TGA Algorishmic Applications in Management.Berlin,2010:220 100 200 300 400 500 600 Hsu C J,Chang C W.Unrelated parallel-machine scheduling with 进化代数 deteriorating jobs and rejection.Appl Mech Mater,2012,263- 图34种算法的收敛曲线 266:655 Fig.3 Conversion rates of the four algorithms [8]Lin F,Zhang X Z,Cai Z X.Approximation algorithms for schedu- ling with rejection on two unrelated parallel machines.Int J Adv Comput Sci Appl,2015,6(11)260 9]Jiang D K,Tan J Y.Scheduling with job rejection and nonsimulta- TGA neous machine available time on unrelated parallel machines.The- or Comput Sci,2016,616:94 [10]Joo C M,Kim B S.Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time CCGA and production availability.Comput Ind Eng,2015,85:102 100 200 300 400 500 600 011 Chen JS,Yang JS.Model formulations for the machine schedu- 进化代数 ling problem with limited waiting time constraints.J Inform Opti- 图4CCGA和TGA的收敛曲线 miz Sci,2006,27(1):225 Fig.4 Conversion rates of CCGA and TGA 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 [13]Wu K J,Lu H W.PCEGA used to solve text feature selection. 析了订单拒绝对总成本的影响，给出了列表拒绝方 Syst Eng Theory Pract,2012,32(10)2215 法和订单拒绝规则.在此基础上，提出了协同进化 (邬开俊，鲁怀伟.采用并行协同进化遗传算法的文本特征 的遗传算法，算法将染色体编码分解为两个个体，分 选择.系统工程理论与实践，2012,32(10)：2215) 别对应订单列表和订单指派，进而采用协同进化策 [14]Li X D,Yao X.Cooperatively coevolving particle swarms for 略对两个个体进行协同式进化操作.根据两个染色 large scale optimization.IEEE Trans Erol Comput,2012,16 (2):210 体个体的不同约束特征，分别对其采用单亲遗传算 [15]Pan QK.An effective co-evolutionary artificial bee colony algo- 法的基因重组算子和传统遗传算法的交叉和变异算 rithm for steelmaking-continuous casting scheduling.Eur J Oper 子进行遗传操作，进而提出了基于列表拒绝方法和 Res,2016,250(3):702 订单拒绝规则的解码方案以及个体评价和选择方 [16]Li M J,Tong T S.A partheno genetic algorithm and analysis on 法.最后，基于大量随机生成的实例展开数据实验， its global convergence.Acta Autom Sin,1999,25 (1):68 (李茂军，童调生.单亲遗传算法及其全局收敛性分析.自 实验结果表明，本文提出的协同进化遗传算法在有 动化学报，1999,25(1)：68) 效性和求解效率方面均有着很好的效果. [17]Wang J L,Huang W B,Ma G W,et al.An improved partheno genetic algorithm for multiobjective economic dispatch in casca- 参考文献 ded hydropower systems.Int Electr Power Energy Syst,2015, [Slotnick S A.Order acceptance and scheduling:a taxonomy and 67:591 review.Eur J Oper Res,2011,212(1)1 [18]Zhu X,Li X P.Iterative search method for total flowtime minimi- Shabtay D,Gaspar N,Kaspi M.A survey on offline scheduling zation no-wait flowshop problem.Int J Mach Learn Cybern, with rejection.Scheduling,2013,16(1):3 2015,6(5):747 B]Angel E,Bampis E,Kononov A.A FPTAS for approximating the [19]Chen C L,Tzeng Y R,Chen C L.A new heuristie based on lo- unrelated parallel machines scheduling problem with costs /Eu- cal best solution for permutation flow shop scheduling.Appl Sof ropean Symposium on Algorithms.Berlin,2001:194 Comput,2015,29:75工程科学学报，第 41 卷，第 4 期 图 3 4 种算法的收敛曲线 Fig． 3 Conversion rates of the four algorithms 图 4 CCGA 和 TGA 的收敛曲线 Fig． 4 Conversion rates of CCGA and TGA 度问题，考虑了最小化总拒绝成本与总拖期成本之 和的优化目标，建立了混合整数线性规划模型，并分 析了订单拒绝对总成本的影响，给出了列表拒绝方 法和订单拒绝规则． 在此基础上，提出了协同进化 的遗传算法，算法将染色体编码分解为两个个体，分 别对应订单列表和订单指派，进而采用协同进化策 略对两个个体进行协同式进化操作． 根据两个染色 体个体的不同约束特征，分别对其采用单亲遗传算 法的基因重组算子和传统遗传算法的交叉和变异算 子进行遗传操作，进而提出了基于列表拒绝方法和 订单拒绝规则的解码方案以及个体评价和选择方 法． 最后，基于大量随机生成的实例展开数据实验， 实验结果表明，本文提出的协同进化遗传算法在有 效性和求解效率方面均有着很好的效果． 参 考 文 献 ［1］ Slotnick S A． Order acceptance and scheduling: a taxonomy and review． Eur J Oper Ｒes，2011，212( 1) : 1 ［2］ Shabtay D，Gaspar N，Kaspi M． A survey on offline scheduling with rejection． J Scheduling，2013，16( 1) : 3 ［3］ Angel E，Bampis E，Kononov A． A FPTAS for approximating the unrelated parallel machines scheduling problem with costs / / Eu￾ropean 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 ［5］ Sengupta S． Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection / / International Work￾shop on Algorithms and Data Structures． Ottawa，2003: 79 ［6］ Miao C X，Zhang Y Z，Wang C F． Bounded parallel-batch sched￾uling 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 ［8］ Lin F，Zhang X Z，Cai Z X． Approximation algorithms for schedu￾ling with rejection on two unrelated parallel machines． Int J Adv Comput Sci Appl，2015，6( 11) : 260 ［9］ Jiang D K，Tan J Y． Scheduling with job rejection and nonsimulta￾neous machine available time on unrelated parallel machines． The￾or Comput Sci，2016，616: 94 ［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 ［11］ Chen J S，Yang J S． Model formulations for the machine schedu￾ling problem with limited waiting time constraints． J Inform Opti￾miz Sci，2006，27( 1) : 225 ［12］ Vallada E，Ｒuiz Ｒ． A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times． Eur J Oper Ｒes，2011，211( 3) : 612 ［13］ Wu K J，Lu H W． PCEGA used to solve text feature selection． Syst Eng Theory Pract，2012，32( 10) : 2215 ( 邬开俊，鲁怀伟． 采用并行协同进化遗传算法的文本特征 选择． 系统工程理论与实践，2012，32( 10) : 2215) ［14］ Li X D，Yao X． Cooperatively coevolving particle swarms for large scale optimization． IEEE Trans Evol Comput，2012，16 ( 2) : 210 ［15］ Pan Q K． An effective co-evolutionary artificial bee colony algo￾rithm for steelmaking- continuous casting scheduling． Eur J Oper Ｒes，2016，250( 3) : 702 ［16］ Li M J，Tong T S． A partheno genetic algorithm and analysis on its global convergence． Acta Autom Sin，1999，25( 1) : 68 ( 李茂军，童调生． 单亲遗传算法及其全局收敛性分析． 自 动化学报，1999，25( 1) : 68) ［17］ Wang J L，Huang W B，Ma G W，et al． An improved partheno genetic algorithm for multi-objective economic dispatch in casca￾ded hydropower systems． Int J Electr Power Energy Syst，2015， 67: 591 ［18］ Zhu X，Li X P． Iterative search method for total flowtime minimi￾zation no-wait flowshop problem． Int J Mach Learn Cybern， 2015，6( 5) : 747 ［19］ Chen C L，Tzeng Y Ｒ，Chen C L． A new heuristic based on lo￾cal best solution for permutation flow shop scheduling． Appl Soft Comput，2015，29: 75 · 835 ·