带机器准备时间的两台同型机复合半在线排序问题

本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法.     

极小化加权完工时间和的Flowshop问题的算法

本文讨论了极小化加权完工时间和的Flowshop问题.我们给出了一个最坏情况误差界为m的启发式算法,对于m=2的情况,如果工件具有一致权因子,即pi相似文献   

带复合信息的三台平行机半在线排序问题

本文讨论在已知加工工件总长度(sum)以及机器带一个缓冲区(buffer)两个复合信息下的同型平行机半在线排序问题． Dosa和He研究了当机器数m=2时的情形,设计出竞争比为5／4的最优半在线算法．本文将其情况推广到三台机器,给出竞争比为4／3的半在线算法,并得到一个11／9的问题下界．     

两台可拒绝同型机半在线排序问题

本文讨论一个两台可拒绝同型机半在线排序问题.当工件到达时,可以被拒绝,但要付出一定的罚值,也可以被接收加工,消耗一定的加工时间.其目标是要使所有加工工件生成的makespan和被拒绝工件的总罚值之和最小.加工不允许中断.进一步,机器带有两个并行处理子系统,可以提供两种排序方案,最后选取较好的一种.这是第一个在可拒绝同型机排序模型中使用半在线信息,我们设计出一个近似算法,其竞争比为3/2,另外又给出一个√3+1/2≈1.366的下界.     

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

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

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

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

工件的释放时间和加工时间具有一致性的单机在线排序问题研究

工件的释放时间和加工时间具有一致性, 是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间, 即若$r_{i}\geq r_{j}$, 则$p_{i}\geq p_{j}$。本文在该一致性约束下, 研究最小化最大加权完工时间单机在线排序问题, 和最小化总加权完工时间单机在线排序问题, 并分别设计出$\frac{\sqrt{5}+1}{2}$-竞争的最好可能在线算法。     

工件的释放时间和加工时间具有一致性的单机在线排序问题研究

工件的释放时间和加工时间具有一致性, 是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间, 即若$r_{i}\geq r_{j}$, 则$p_{i}\geq p_{j}$。本文在该一致性约束下, 研究最小化最大加权完工时间单机在线排序问题, 和最小化总加权完工时间单机在线排序问题, 并分别设计出$\frac{\sqrt{5}+1}{2}$-竞争的最好可能在线算法。     

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

本讨论资源有限的加权总工时间单机排序问题，对现在仍为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的最优算法。     

极小化总加权完工时间的Dial-a-Ride问题的在线随机算法

讨论一般度量空间上带单服务器的极小化总加权完工时间在线Dial-a-Ride问题.通过应用贪婪区间的技巧,提出了一个一般在线随机算法.根据这个算法,对于容量为1或者任意容量的一般度量空间上的在线Dial-a-Ride问题能得到一个竞争比为(2+√2)/ln(1+√2)的在线随机算法,这个算法不仅具有当前最好的竞争比,而且也改进了Krumke等人的结果.     

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

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

加工时间可控单机加权总完工时间Pareto优化研究

针对单机环境最优化加权总完工时间问题,当工件加工时间可通过分配资源进行压缩时,研究对工件的加工次序和时间压缩量的优化,从而权衡调度性能目标和资源成本目标。调度性能目标为压缩后工件的加权总完工时间,资源成本目标为工件压缩量的线性函数。此问题复杂性已被证明为NP-hard,为弥补较少有研究从Pareto优化角度求解该问题有效前沿的不足,针对经典NSGA-II求解时易早熟收敛的特点,采用算法混合方式进行优化方法研究。融合归档式多目标模拟退火算法跳出局部极值的优势,启用外部存档策略提升种群的多样性,采用主从模式的并行结构提升求解效率。最后为检验优化方法的有效性,一方面通过对Benchmark测试函数ZDT1-6的求解,表明混合算法对不同结构和形状目标函数兼具普适性和有效性;另一方面结合问题特点设计有效编码方式,针对随机生成算例进行求解。通过分析有效前沿收敛性和多样性,验证了所提方法对于优化加工时间可控单机加权总完工时间问题的有效性。     

Bicriteria Scheduling on a Series-Batching Machine to Minimize Makespan and Total Weighted Completion Time with Equal Length Job

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.     

Preemptive Scheduling with Availability Constraints to Minimize Total Weighted Completion Times

In this paper we study the problem of scheduling n jobs on a single machine with availability constraints. The objective is to minimize total weighted job completion times. We show that the problem is NP-hard in the strong sense. Then we consider two intractable special cases, namely, proportional weight case, and single availability constraint case. We propose two heuristics for these cases and analyze their worst-case error bounds.     

带折扣因子的单机干扰管理研究

针对可预见的干扰管理问题,考虑单机环境下,加权折扣最短加工时间优先(WDSPT)序为原目标的最优加工次序,研究了如何对初始加工时间表进行修改。在干扰事件影响下,初始加工时间表将不再是最优,甚至不再可行。和大多数重排序研究不同,构建了同时考虑原目标和由干扰事件造成的扰动目标的重排序模型,并基于理想点法提出一种动态规划算法来求解所建模型中的双目标排序问题。最后通过一个数值算例来说明该重调度模型对于求解带折扣因子的单机干扰管理问题是有效的。     

Single Machine Scheduling and Selection to Minimize Total Flow Time with Minimum Number Tardy

Emmons considered the problem of sequencing N jobs on a single machine to minimize total flow time with the minimum number of tardy jobs. He proposed an effective branch-and-bound algorithm for this problem. In this paper, we show that Emmons' algorithm can be extended to a more difficult scheduling problem which includes an optimal selection of jobs as well.