并行多机开放车间调度问题的模型与算法

发光二极管制造过程中,晶粒分类拣选工序的调度问题是典型的并行多机开放车间调度问题,属于NP-hard问题。研究了该调度问题以最小化总加权完工时间为目标的求解模型与算法。根据问题特性构建了可获得最优解的混合整数规划模型,并设计了同时考虑质量与求解效率的启发式算法和改进粒子群优化算法。仿真结果显示,启发式算法和改进粒子群优化算法都能在合理的时间内迅速有效地获得较佳的调度解。

自由作业环境下的供应链排序

本文研究了一类集成工件加工和发送的供应链排序模型.利用排序理论和动态规划方法,获得了两机器情形下的供应链排序问题的多项式时间近似算法,并证明算法的性能比为2.

依赖机器的两台机自由作业排序问题

研究加工时间仅依赖于机器的两台机自由作业排序问题O_2|p_(ij)=p_i,p_2<p_1<2p_2,Non-Idle|ΣC_j.项思明和唐国春(1998)证明了可将该问题转化成指派问题.俞文(?)和应刚(1998)给出了这一问题的显式解,并用较长的篇幅证明其显式解的正确性;他们还举例说明所给出的显式最优排序并不排除其他形式的最优解的存在;但他们未说明所给出的显式解何时才是唯一最优解.将给出问题O_2|p_(ij)=p_i,p_2<p_1<2p_2,Non-Idle|∑C_j的显式解的直观的最优性证明,并讨论问题显式解何时是唯一的最优解.

基于改进遗传算法的民航客机地勤调度问题

开放车间调度是众多车间调度中的一类问题,在工业与服务业中有着广泛的应用。民航客机地勤保障调度问题是典型的开放车间调度问题。以最大完工时间最小化为目标,根据问题特性,将元启发式算法中的遗传算法应用于开放车间调度问题中,构建可获得最优解的混合整数规划模型,设计算法操作流程并分析优化方案。实验结果证实,设计方案各个工序的实际加工时间均符合实例的相应数据,说明该调度方案是合理的。

具有准备时间和延迟时间的自由作业问题的复杂性

讨论具有准备时间和延迟时间的自由作业问题 。

自由作业问题的一种启发式算法及最坏性能比分析

研究具有准备时间的自由作业问题 ,给出一种简单的启发式算法 ,证明在此启发式算法下 ,最坏性能比是 2 - 1/m(其中m是机器的台数 ) ,且上界是紧的 .从而证明了对该问题的猜想 :即在贪婪算法的情况下其最坏性能比是 2 - 1/m(其中m是机器的台数 ) ,且上界是紧的 .特别当m =2时 ,具有准备时间的自由作业问题 ,利用该启发式算法得到的最坏性能比是 3/ 2 ,其上界也是紧的 .

具有优先权的自由作业时间表问题研究

研究了具有优先权的自由作业时间表问题,在工件具有准备时间的条件下,给出一种新的启发式算法,其最坏性能比不超过2,猜想该算法的紧界是2-2/(m+1),其中m是机器的台数.证明在3台机器的情况下,该算法的最坏性能比为3/2,且上界是紧的.

关于二台机器自由作业的总流程问题

二台机器自由作业的总流程问题是NP困难问题．当加工时间仅依赖于机器时，该问题尚未被解决．本文对于机器均不允许空闲的约束条件下的上述问题，给出了显式解，即最优时间表的构造形式，从而改进了文献中的结果．此外，本文还对允许空闲的上述问题，作了一些讨论，指出了Vakharia和Catay一文（1997）中算法的错误．

多目标混合进化算法求解加工时间可控的开放车间调度问题

开放车间调度问题属于典型的NP-hard问题。目前的相关研究大多假设工序在机器上具有固定的加工时间。然而,在大多数现实生产场景中,机床的加工时间可以通过调节加工功率加以控制。同时优化完工时间和总能耗两个冲突目标对高效、节能的开放车间生产具有重要意义。为此,研究了可控加工时间的多目标开放车间调度问题(MOOSPCPT),以最小化完工时间和总额外能耗为目标构建了混合整数规划模型,并提出一种多目标混合进化算法(MOHEA)用于求解MOOSPCPT。在MOHEA中提出多个策略:(1)改进生物地理学优化算法中的迁移策略和变异策略用于全局搜索,有效地提高了种群的多样性;(2)基于关键路径设计一种自调整变邻域搜索策略,增强了算法的局部搜索能力;(3)设计了一种加工时间重置算子,从而显著提升了算法的搜索效率。仿真实验结果表明:所提出的策略有效地提升了算法性能;相较于NSGA-Ⅱ(Non-dominated Sorting Genetic AlgorithmⅡ)、NSGA-Ⅲ(Non-dominated Sorting Genetic Algorithm Ⅲ)和SPEA2(Strength Pareto Evolutionary Algorithm 2),MOHEA能够更有效地解决MOOSPCPT。

自由作业环境下的供应链排序问题

本文研究自由作业环境下的供应链排序问题,研究供应链的上游如何安排工件在自由作业机器上加工,把加工完毕的工件分批发送给下游,使得生产排序费用和发送费用总和最少.这里,生产排序费用是用工件送到时间的函数来表示;发送费用是由发送的固定费用和与运输路径有关的变化费用所组成.本文研究以工件最大送到时间为生产排序费用的自由作业供应链排序问题,在指出问题的NP困难性后,用动态规划算法构造多项式时间近似算法,并分析算法的性能比.本文最后还对特殊情形进行了讨论.

带单服务器的自由作业排序问题的启发式算法

研究带单服务器的自由作业排序问题,证明在只有两台机器且加工时间相同的情况下该问题是强NP-困难的,引入了求解该问题的启发式算法,证明该算法的紧界为5/4.在具有m台机器的情况下,给出相应的启发式算法,其紧界为2-3/(m+2).