带准备时间和强制工期的单机排序问题

讨论了带准备时间和强制工期的单机排序问题.在工件可中断、机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,首先考虑了问题的可行性.通过将问题转化为一个带容量限制的有向图,并运用求解最大网络流的算法,提出了判定问题可行性的方法.对于可行问题,给出了一个算法在多项式时间内获得最优排序.

极小化最大提前完工时间的单机排序问题

工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.基于此,讨论了带准备时间和强制工期的n个工件在单机上加工,在机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,考虑了工件加工时间相等的特殊情形.先讨论问题的可行性,针对可行问题,提出了一个算法在多项式时间内获得最优排序.

极小化最大提前完工时间的两平行机排序问题

讨论了在两台同型平行机上,加工带截止期限的n个工件,在机器可空闲条件下,确定一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会无可行排序.先讨论问题的可行性,通过子集和问题归约,证明了判定问题的可行性是NP-complete的.如果问题可行,接着讨论了问题的复杂性,通过划分问题归约,证明了其是NP-complete的.最后,考虑了工件加工时间相等的特殊情形,提出了一个算法在多项式时间内获得最优排序.

带强制工期的单机排序问题

讨论了带强制工期的n个工件在单机上加工,在允许机器空闲的条件下,使得最大提前完工时间最小。由于工件不允许延迟,问题可能会无可行排序。先讨论问题的可行性。如果问题可行,找出一个可行序列作为预排序列,并给出一个算法计算出每个工件尽可能迟的开工时间,而后判断预排序列是否为最优,如果不能直接确定为最优,则给出一个算法在多项式时间内尝试由预排序列开始,通过不断调整工件的次序来获得最优排序。

基于动态规划的分批排序算法

研究了在给定截止期限(deadline)下的单机分批(batch)排序问题,目标函数是最大提前完工时间。由于工件不能延迟,因此先讨论了问题可行解的存在。当问题有可行解时,证明了工件按最早截止期限(Earliest Deadline,ED)规则的排序是一个最优排序,接着给出一个时间复杂度为O(n3)的动态规划算法来获得最优分批。

带强制工期的双机开放车间排序问题

讨论了强制工期相等的n个工件在双机开放车间加工。在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小。由于工件不允许延迟,问题可能会无可行排序。先讨论了问题的可行性。如果问题可行,找出一个可行序列作为预排序列,并提出了一个算法计算每个工件尽可能迟的开工时间。而后,提出了一个多项式时间最优算法,在预排序列的基础上,通过调整两台机器上最先加工的工件来获得最优排序。

强制工期相等的双机流水车间排序问题

讨论了强制工期相等的n个工件在双机流水车间的加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会不可行排序.先讨论问题的可行性,如果问题可行,找出一个可行序列作为预排序列,并给出一个算法计算出每个工件尽可能迟的开工时间,而后,给出一个多项式时间算法,在预排序列的基础上,通过调整最先加工的工件来获得最优排序.

带强制工期的可中断平行机排序问题

讨论了在m台同型平行机上,加工带强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,讨论了强制工期相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序.先讨论了可行性,接着针对可行问题,提出一个算法在多项式时间内获得最优排序.

带强制工期的可中断单机排序问题

工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过奇偶划分问题归约,证明了其是NP-complete的.而后,讨论了加工时间相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序,因此提出了—个多项式时间算法,既能判定可行性,又能针对可行问题获得最优排序.