带有退化、拒绝和不可用区间的恒速机排序

考虑带有退化工件、拒绝和不可用区间的2台恒速机排序问题,其中一台机器上带有一段固定的不可用区间。该问题以实际生产环境为背景来研究机器的工件调度问题。在此模型中,每个工件的实际加工时间与它的基本加工时间、退化率和开始加工时间有关,工件的实际加工时间是其开始加工时间的线性递增函数,工件可以被拒绝,被拒绝的工件需要支付惩罚成本,在不可用区间内,机器无法加工工件。目标是极小化接受工件的最大完工时间与被拒绝工件的总拒绝惩罚之和。对于这个NP-难问题,在不可用区间前、后及另一台机器上,工件按{aj/bj}不减顺序排列可以得到最优解,通过过程划分的方法,提出了一个完全多项式时间近似策略(FPTAS),最后确定了其时间复杂性为O(n^(6)L^(4)/ε^(3))。

加工时间可控的单机工期分配问题

研究带有学习效应、恶化效应和资源分配的单机工期分配问题。该问题以实际生产环境为背景来研究机器的工件调度问题。在此模型中,工件的学习效应与工件的加工位置相关,工件的恶化效应与工件的开始加工时间线性相关,资源分配为凸函数。讨论了在凸性资源分配的情况下,带有学习效应、恶化效应和资源分配的工期分配问题。从CON、SLK、DIF 3种不同的工期分配的角度分析这个问题:针对CON、SLK、DIF 3种不同工期分配问题中的每一种,均提出相应多项式时间内的最优算法。目的是确定最优排序、资源分配量以及工件的加工顺序,使包含提前、延误、工期、总资源消耗的函数最小。通过将其转换为指派问题,证明这些问题都是多项式时间可解的。

带有退化、拒绝和不可用区间的恒速机排序问题

考虑带有退化工件、拒绝和不可用区间的两台恒速机排序问题,其中第一台机器上有一个固定的不可用区间,每个工件的加工时间是它开始加工时间的简单的线性递增函数,一个工件可以通过支付惩罚而被拒绝.目标是极小化接受工件的总完工时间与被拒绝工件的总惩罚之和.对于这个NP-难问题,提出了一个全多项式近似策略(FPTAS).