基于遗传算法的最小误工任务数问题求解

为了解决最小误工任务数问题（MTTP），将遗传算法引入该问题的求解中，基于惩罚函数。讨论了MTTP的遗传算法求解方法。并对genGA，ssGA，cGA三种演化式算法求解MTTP的实验运行结果进行分析比较，得出在解决大规模的MTTP时，genGA明显优于另两种演化式算法。     

运筹学与控制论两台平行机环境下加工时间退化的可拒绝排序问题

研究两台平行机环境下加工时间线性退化的可拒绝排序问题，工件的实际加工时间是关于该工件开始加工时间的线性函数，每个工件都有一个独立的截止工期，在截止工期之前或之后完工的任务将分别受到提前和误工工件惩罚。工件允许被拒绝，如果工件被拒绝则需要支付一定的拒绝费用。目标是分别确定接受工件和拒绝工件的任务集合，找到接受任务的最优排序和每个被接受工件的最优任务工期最小化工期、误工工件惩罚、总完工时间以及被拒绝工件的惩罚费用之和。证明了此 NP 难问题可以通过动态规划方法求得最优解，并通过动态规划运用简化执行空间的方法给出了复杂度为o(n5D2/ε2)的全多项式近似策略（FPTAS），其中 n 表示工件的数量，ε 是允许误差界。
     

部分工件必须不误工的误工排序问题

排序论中使误工工件的个数为最少的单台机器排序问题,称为误工问题,是排序论中最基本的问题之一.1973年,Sidney研究在工件的一个子集T中的工件必须不误工的条件下,使误工工件的个数为最少的误工排序问题1｜T｜∑Uj,并且给出该问题复杂性为O(n log n)的多项式算法--Sidney算法.本文把Sidney 算法改写成比较简洁的算法1,1)步骤1:设E 0=T,J－E 0=｛j1,j2,…,jm｝,j1＜j2＜…＜jm,m=n-｜T｜,令k=1:2)步骤2:若k=m+1,算法终止,(Em,J－Em)就是最优排序:若k＜m+1,转入步骤3:3)步骤3:设Fk=Ek-1∪{jk},计算Ek如下:如果Fk是不误工子集,令Ek=Ek-1∪{jk}:否则,如果Fk不是不误工子集,令Ek+Fk\{jr}.其中工件jr的加工时间为pr=max{pi｜ji∈Fk\T}.Ek中的工件是按EDD序排列.k=k+1,转入步骤2.并用数学归纳法证明算法1产生的排序是该误工问题的最优解.     

平行机最小化误工损失调度问题的粒子群算法

【目的】讨论非同类机环境下最小化任务总误工损失的调度问题。任务的误工损失是与交付期有关的一种惩罚量,该惩罚量的值等于任务滞后于交付期加工的部分。【方法】设计了一个粒子群算法求解该问题,并以数值实验进行验证。【结果】针对问题特性,对粒子群算法中的粒子表达方式、运算操作、初始解生成、种群更新方法等进行了重新定义。【结论】数值实验表明,算法处理该问题时可获得性能良好的解,并且运行时间也在可接受范围之内。
     

P与d一致时的分族分批排序误工个数问题

研究了一类分族分批排序最小误工个数问题,给出并证明了最优排序的性质,证明了此问题是NP-困难的．对工件的到达时间和工期一致时的情形,给出了一个时间复杂性为O（mb（n/m）^2m）的动态规划算法．     

基于订单完成的柔性流水作业排序

按订单进行生产安排符合大多数实际应用,研究基于订单完成的柔性流水作业排序问题,考虑工件的订单属性,以最小化订单的加权误工成本为目标来进行柔性流水作业的排序,给出了具体的排序算法。     

误工排序问题的研究

误工排序问题是经典排序论中最基本和最重要的问题.40年来国内外许多学者对其进行研究的兴趣有增无减,深刻的成果不断涌现.本文阐述2006年以来重庆师范大学运筹学与控制论专业的硕士研究生在研究误工排序问题上得到的成果及其意义.这些成果包括研究经典的和推广的误工问题,包括某些工件必须不误工,或者工件的就绪时间不相同、与交货期有一致性的,或者带权的误工排序问题,或者工件的加工时间与工件的权有反向一致性,或者多台平行机误工排序问题等等得到的成果.     

关于误工的两个代理单机排序问题

【目的】研究与误工相关的两个代理单机排序问题。【方法】第一个代理工件的到达时间与工期满足一致关系,目标函数为总误工或最大误工。第二个代理工件可中断,目标函数为总误工工件个数,在模型确定的情况下结合Lawler算法或EDD规则确定一个最优排序规则,使得满足第二个代理目标可行的情况下,第一个代理的目标函数值最小。【结果】在上述模型最优排序规则确定的前提下,求出最优排序方案使得第一个代理的目标函数最小。【结论】提出了总误工问题的一个拟多项式时间动态规划算法,给出了最大误工问题时间复杂度的证明。