原始工件的完工时间限制下的最小化最大延误时间的重新排序

考虑由两个代理引起的重新排序问题,其中每个代理都在公共的加工资源下完成各自的不可中断加工的工件.每个代理要求在仅依赖工件的完工时间时最小化某一个特定的目标函数.考虑在原始工件的完工时间限制下的两个代理的单机最小化最大延误时间的重新排序问题.证明了该问题能在多项式时间或者拟多项式时间内解决.     

具有禁用区间的单机最小化加权完工时间和排序问题

研究具有禁用区间的单机最小化加权完工时间和排序问题.在该问题中,有一些禁用区间已经固定在机器上,工件将被安排在其余自由区间内进行加工且不能与禁用区间重叠.在文献中已经证明,该问题是强NP-困难的,并且在P不等于NP的假设下,该问题不存在2~(q(n))-近似算法.其中,n是工件个数,而q(n)是n的任一多项式.但是,其精确最优算法尚属未知.给出了该问题的一个动态规划最优算法.当禁用区间的数目是固定常数时,该算法是拟多项式的.     

同时最小化具有相等加工时间的最大完工时间和加权总完工时间的序列分批排序问题(英文)

It is known that the problem of minimizing total weighted completion time on a series-batching machine is NP-hard. We consider a series-batching bicriteria scheduling problem of minimizing makespan and total weighted completion time with equal length job simultaneously. A batching machine can handle up to b jobs in a batch, where b is called the batch capacity of the machine. We study the unbounded model with b ≥ n, where n denotes the number of jobs. A dynamic programming algorithm is proposed to solve the unbounded model, which can find all Pareto optimal schedules in O(n3) time.     

同时最小化最大费用和最大完工时间的双代理无界平行分批排序

有两个代理A和B, 每个代理都各自有一个工件集. 同一个代理的工件可以在同一批中加工, 而且每一个代理都有一个需要最小化的函数. 研究在无界平行分批处理机上同时最小化代理A的最大费用和代理B的最大完工时间问题, 并给出一个算法, 它可在多项式时间内找到关于这个问题的所有Pareto最优点.     

单可变资源最小化加权完工时间和排序问题的强NP-困难性

Baker和Nuttle提出了下述单可变资源排序问题：扎个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小,而资源的可利用率是随着时间而变化的．当最小化的目标函数是工件的加权完工时间和时,Baker和Nuttle猜测该问题是NP-困难的．最近,Yuan、Cheng和Ng证明该问题在一般意义下是NP-困难的,但是问题的精确复杂性仍然是悬而未决的．本文我们证明了该问题是强NP-困难的．     

单可变资源最小化加权完工时间和排序问题的强NP-困难性

Baker和Nuttle提出了下述单可变资源排序问题：$n$个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小,而资源的可利用率是随着时间而变化的.当最小化的目标函数是工件的加权完工时间和时,Baker和Nuttle猜测该问题是NP-困难的.最近,Yuan、Cheng 和 Ng 证明该问题在一般意义下是NP-困难的,但是问题的精确复杂性仍然是悬而未决的.本文我们证明了该问题是强NP-困难的.     

序列错位限制下最小化完工时间和的继列分批重新排序

在单机分批排序中,一个原始工件集已经分好批排好顺序,使得给定的目标函数最小.当一个新的工件集到来时,决策者需要插入这些新工件到原来的顺序中,这样使得原始工件就会产生一些错位.但为了满足对原始工件集的要求而不过分的打乱它们的顺序的条件下,使得新的目标值为最优.本文主要研究的是在序列错位量限制的条件下,继列分批最小化总完工时间的重新排序问题,对于最大序列错位和总序列错位的不同约束情况下,研究可行排序和最优排序的结构性质,进而设计了它们的多项式时间算法.     

基于重新排序时间错位限制下的最小化总完工时间的平行分批排序（英文）

In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. A batching machine is a machine that can handle up to some jobs simultaneously. In this paper,we consider the total completion time under a limit on the sequence disruptions for parallel batching based on rescheduling. For the parallel batching problem based on rescheduling, we research the properties of feasible schedules and optimal schedules on the total completion time under a limit on the maximum time disruptions or total time disruptions, in which the jobs are sequenced in SPT order, and give out the pseudo-polynomial time algorithms on the number of jobs and the processing time of jobs by applying the dynamic programming method.     

加工时间和尺寸成正比单机排序和工件运输的最小化最大完工时间问题

在单机排序和工件运输的最小化最大完工时间问题中,工件首先在一台机器上加工,然后被一辆有容量限制的汽车运送到一个顾客．当工件的加工时间和尺寸无关时, Chang和Lee已经证明该问题是强NP困难的．他们也给出了一个启发式算法,它的最差执行比为5／3,并且这个界是紧的．本文考虑工件的加工时间和尺寸成正比的情形,证明了Chang和Lee的算法有更好的最差执行比53／35,并提供了一个新的启发式算法,它的最差执行比是3／2,并且这个界是最好的．     

加工时间可控和恶化的单机最大完工时间排序

本文研究加工时间可控并随开工时间简单线性增长的单机最大完工时间排序问题.该问题将加工时间可控排序和加工时间恶化排序两类研究连接到一起.通过比较技术证明了该问题存在满足以下性质的最优解:每个工件的加工时间或者完全压缩,或者完全不压缩;加工时间完全压缩的工件的顺序由一个工件参数和控制变量的函数的递增序给出,完全不压缩的工件在完全压缩的工件之后以任意序加工.通过将问题等价转换为0-1非线性整数规划问题,给出了单机排序问题的贪婪算法.     

极小化加权总完工时间的分批排序问题

本文讨论了分批排序中极小化加权总完工时间的两个问题.就所有工件的加工时间都相等这一特殊情况,分别给出两个算法,并证明了算法的最优性.     

资源有限的加权总完工时间单机排序问题

本讨论资源有限的加权总工时间单机排序问题，对现在仍为OPEN问题1｜pj=bj-ajuj，∑uj≤U｜∑wjCj给出了一个有关最优解中最优资源分配的重要性质，并利用该性质分别给出了三种情况bj=b,wj=w,aj=a；bj=b,wj=w,uj=u；aj=a,wj=w,uj=u的最优算法。     

目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法

本文研究了两台机器带柔性维修时间限制的排序问题,其中第一台机器在固定的时间内必须进行维修,而第二台机器一直可用,目标是最小化所有工件的最大完工时间。工件在加工过程中不允许中断。对于该问题,我们给出了一个性能比为的近似算法,并证明了该性能比是紧的。     

基于重新排序的退化工件最小化总延误时间问题

考虑了错位限制下的含有退化工件的重新排序问题,即工件的实际加工时间看作是工件开工时间的线性函数．重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达,新工件的安排使得原始工件重新排序进而产生错位．研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题,其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率αj非减的序列排列,基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法．     

加权完工时间和的调整时间可分离Flow shop排序问题

讨论了2台机器调整时间可分离的FlowShop排序问题,目标函数为极小化加权完工时间和.给出了对于一种特殊情况,问题存在多项式最优算法的充分条件.接着又给出了求解该问题的一个分枝定界法.     

折扣加权总完工时间问题的半在线排序算法

讨论到达时间任意,加工时间具有上下限约束,目标函数为带折扣的加权总完工时间的单机排序问题1|rj,Pmin≤Pj≤Pmax|∑ωj(1-e-βCj),给出了此问题在任意半在线算法下的竞争比下界,并提出了求解此问题的一种半在线算法D-αWDSPT,通过分析算法竞争比说明该算法是一种近似最优算法.同时指出,算法在问题的三种特殊情况下是最优算法.第一种问题是最小加工时间P→0,第二种问题是折扣因子β→0,第三种问题是工件加工时间相同Pmin=Pmax     

最小化总完工时间与分批费用之和的有界分批排序问题

考虑了当每分一批均产生固定费用、批容量有界且为固定值b、加工不允许中断抢先.所有工件在零时刻到达时的单机平行分批排序问题.目标是最小化总完工时间与分批费用之和.利用动态规划方法给出了多项式时间算法,时间界为O(n~(b(b-1))).     

工件可自由下线最小化总完工时间的平行分批排序问题

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法.     

工件可自由下线最小化总完工时间的有界平行分批排序

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题.在该问题中,一台平行批机器可以同时处理b个工件作为一个平行批,这里b是批容量,一个批的加工时间等于分配给这个批的工件的最大加工时间.关于可自由下线工件,每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和.也就是,如果一个批■有一个开工时间S,那么包含在批■中的每一个工件乃的开工时间定义为S,而它的完工时间定义为S+p_j,这里p_j是工件J_j的加工时间.对此问题,首先研究最优排序的一些性质.然后,基于这些性质,给出一个运行时间为O(n~(b(b-1))的动态规划算法.     

无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案

本文考虑n个工件的无限批量机器调度问题．一台机器可以同时加工B≥n个工件．每个工件具有一个正权因子、一个释放时间和一个加工时间．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间，即它们的共同开始时间加上该批次的加工时间．对于最小化加权完工时间和问题，本文给出了第一个多项式时间近似方案(PTAS)．对任意给定精度，该算法的运行时间为线性的．