Q2‖Cmax的对偶近似算法

本文讨论两台同类平行机排序问题,首先给出Ｍｕｌｔｉｆｉｔ算法在不同迭代初值下的紧界,然后利用一个新设计的对偶贪婪子过程构造出线性时间６／５－复合近似算法。     

EXACT BOUNDS OF THE MODIFIED LPT ALGORITHMS APPLYING TO PARALLEL MACHINES SCHEDULING WITH NONSILMULTANEOUS MACHINE AVAILABLE TIMES

In this paper, we consider Parallel Machines Scheduling with nonsimultaneous machine available time. We give the exact worst case performance bound of MLPT proposed by Lee. Furthermore, two other modified LPT algorithms are discussed. The paper is ended by numerical ex-periments of these algorithms.     

Parallel machine covering with limited number of preemptions简

In this paper,we investigate the i-preemptive scheduling on parallel machines to maximize the minimum machine completion time,i.e.,machine covering problem with limited number of preemptions. It is aimed to obtain the worst case ratio of the objective value of the optimal schedule with unlimited preemptions and that of the schedule allowed to be preempted at most i times. For the m identical machines case,we show the worst case ratio is 2m.i.1 m,and we present a polynomial time algorithm which can guarantee the ratio for any 0 ≤ i ≤ m. 1. For the i-preemptive scheduling on two uniform machines case,we only need to consider the cases of i = 0 and i = 1. For both cases,we present two linear time algorithms and obtain the worst case ratios with respect to s,i.e.,the ratio of the speeds of two machines.     

具有机器适用限制的分布式置换流水车间问题的模型与算法

考虑具有机器适用限制的多个不同置换流水车间的调度问题. 机器适用限制指的是每个工件只能分配到其可加工工厂集合. 所有置换流水车间拥有的机器数相同但是具有不同的加工能力. 首先, 针对该问题建立了基于位置的混合整数线性规划模型; 进而, 对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法. 其次, 基于NEH方法提出了启发式算法NEHg, 并给出了以NEHg为上界的分支定界算法. 最后, 通过例子说明了NEHg启发式算法和分支定界算法的计算过程, 并进行大量的实验将NEHg与NEH算法结果进行比较, 从而验证了NEHg算法的有效性.     

两台平行机完工时间平方和最小的排序问题

在两个竞争公司进行零和博弈过程中, 最大化两个公司收益的乘积, 在两台平行机的离线排序问题中相当于最小化两台机器完工时间的平方和. 给出了该问题修改的延缓开始\ LPT\ 算法: 首先, 将工件按照加工时间$\p_j\ $的\ LPT\ 序重新标记; 若加工时间最长的前\ $2m$\ 个工件的总加工时间\ $P(2m)< (2m+1)p_{2m+1}$, 最优的安排加工前\ $2m+1$\ 个工件, 一旦有机器空闲, 依次从第\ $2m+2$\ 个工件安排加工; 否则,\ $P(2m)\geq (2m+1)p_{2m+1}$, 最优的安排加工前\ $2m$\ 个工件, 一旦有机器空闲, 依次从第\ $2m+1$\ 个工件安排加工. 证明了该算法的最差性能比不超过\ $1+ ( \frac{1}{2m+2} )^2$, 且界是紧的.     

堆取料机调度问题的一个近似算法

研究源自煤炭港口料场管理的堆取料机调度问题.该问题中,堆取料机从长为L的料场作业区最左端开始空机或载料运行,两者的速度之比为s：1（s ≥ 1）.决策者需确定储料堆在作业区的分布以及堆取料机处理它们的先后次序,目的是极小化一批煤料运输船的在港服务时间.考虑堆取料机处理完毕需要回到料场终端的作业模型,证明了存在最坏情况界不超过1+1/4s的近似算法.     

可拆分平行机排序问题研究

平行机排序问题是把n个产品安排到m台机器上加工，使其总费用最小．通常的平行机排序问题都假设（C1）：任何产品不能在不同机器上同时加工．但是，如果把产品的加工时间看成一个产品量的需求，就可以假设（C2）：允许同一产品拆分在不同机器上同时加工．本文首先回顾了C1假设下平行机排序问题已有的结果，然后基于假设C2，讨论了各种费用目标下问题的算法及其复杂性．在没有生产准备时间的情况下，给出了一些问题的多项式算法和线性规划方法．在有独立生产准备时间的情况下，给出了P／split／Cmax问题的启发式算法及其算法分析．     

Single machine scheduling with forbidden start times

This paper addresses a single machine scheduling problem in which the following simple constraint is added: a set of time slots is forbidden for starting a task, that is no task can start at any forbidden time point. We show that the single machine problem with makespan minimization is strongly -complete and we give polynomial algorithms to solve the problems with a small number of forbidden start times.      

An improved heuristic for one-machine scheduling with delays constraints

An improved heuristic is proposed for one-machine scheduling problem with delay constraints, thus an open problem raised by Wikumet al. is solved. The heuristic solves the corresponding unit-execution-time problem optimally.     

Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem

This paper deals with an unrelated machine scheduling problem of minimizing the total weighted flow time, subject to time-window job availability and machine downtime side constraints. We present a zero-one integer programming formulation of this problem. The linear programming relaxation of this formulation affords a tight lower bound and often generates an integer optimal solution for the problem. By exploiting the special structures inherent in the formulation, we develop some classes of strong valid inequalities that can be used to tighten the initial formulation, as well as to provide cutting planes in the context of a branch-and-cut procedure. A major computational bottleneck is the solution of the underlying linear programming relaxation because of the extremely high degree of degeneracy inherent in the formulation. In order to overcome this difficulty, we employ a Lagrangian dual formulation to generate lower and upper bounds and to drive the branch-and-bound algorithm. As a practical instance of the unrelated machine scheduling problem, we describe a combinatorial naval defense problem. This problem seeks to schedule a set of illuminators (passive homing devices) in order to strike a given set of targets using surface-to-air missiles in a naval battle-group engagement scenario. We present computational results for this problem using suitable realistic data.     

工件的运输和继列分批加工协作排序问题

近年来,工件的运输和加工协作排序问题在物流和供应链管理领域得到广泛关注. 讨论了先用 $\ m$ 台车辆将工件从等待区域运输到继列分批处理机处, 再进行分批加工的协作排序问题, 加工一批工件需要支付一定的费用, 目标为最小化工件的总完工时间与批的加工费用之和. 在工件的加工时间都相等的情况下, 如果工件运输方案确定, 给出了多项式时间的动态规划算法; 如果工件运输方案不确定, 证明了该问题是{\, NP}-难的, 给出了车辆返回时间 $\ t=0$ 时, 最差性能比等于 $\ 2-\frac{1}{m}$ 的近似算法.     

Order acceptance and scheduling with machine availability constraints

We consider an order acceptance and scheduling model with machine availability constraints. The manufacturer (machine) is assumed to be available to process orders only within a number of discontinuous time intervals. To capture the real-life behavior of a typical manufacturer who has restrictions of time availability to process orders, our model allows the manufacturer to reject or outsource some of the orders. When an order is rejected or outsourced, an order-dependent cost of penalty will occur. The objective is to minimize the makespan of all accepted orders plus the total penalty of all rejected/outsourced orders. We study the approximability of the model and some of its important special cases.     

Single machine scheduling with semi-resumable machine availability constraints

This paper considers the semi-resumable model of single machine scheduling with a non-availability period. The machine is not available for processing during a given time interval. A job cannot be completed before the non-availability period will have to partially restart after the machine has become available again. For the problem with objective of minimizing makespan, the tight worst-case ratio of algorithm LPT is given, and an FPTAS is also proposed. For the problem with objective of minimizing total weighted completion time, an approximation algorithm with worst-case ratio smaller than 2 is presented. Two special cases of the latter problem are also considered, and improved algorithms are given.     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

机器和工人都有加工资质约束的平行机排序问题研究

研究一类新型的平行机排序问题, 即在机器和工人都是必需的加工资源并且都有加工资质约束的情况下, 如何在一组平行机上进行工件排序(或称调度)以最小化时间表长C_max. 将研究工件加工时间均为单位时间的情况, 通过建立网络流模型以及采用二分搜索技术, 可以在多项式时间内精确地求解上述问题, 算法复杂度为O(n^{3}logn). 同时提供了一种基于双重动态柔性选择\,(DDFS)\,策略的启发式算法,可以获得较好的排序效果, 算法复杂度为O(n^{2}).     

Single machine group scheduling with ordered criteria

The single machine group scheduling problem is considered. Jobs are classified into several groups on the basis of group technology, i.e. jobs of the same group have to be processed jointly. A machine set-up time independent of the group sequence is needed between each two consecutive groups. A schedule specifies the sequence of groups and the sequence of jobs in each group. The quality of a schedule is measured by the criteriaF ₁, ...,F _m ordered by their relative importance. The objective is to minimize the least important criterionF _m subject to the schedule being optimal with respect to the more important criterionF _m–1 which is minimized on the set of schedules minimizing criterionF _m–2 and so on. The most important criterion isF ₁, which is minimized on the set of all feasible schedules. An approach to solve this multicriterion problem in polynomial time is presented if functionsF ₁, ...,F _m have special properties. The total weighted completion time and the total weighted exponential time are the examples of functionsF ₁, ...,F _m–1 and the maximum cost is an example of functionF _m for which our approach can be applied.The research of the authors was partially supported by a KBN Grant No. 3 P 406 003 05, the Fundamental Research Fund of Belarus, Project N 60-242, and the Deutsche Forschungsgemeinschaft, Project Schema, respectively. The paper was completed while the first author was visiting the University of Melbourne.     

Approximation schemes for parallel machine scheduling with availability constraints

We investigate the problems of scheduling n weighted jobs to m parallel machines with availability constraints. We consider two different models of availability constraints: the preventive model, in which the unavailability is due to preventive machine maintenance, and the fixed job model, in which the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that m is a constant, and that the jobs are non-resumable.For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even if w_i=p_i for all jobs. In this paper, we assume that there is one machine that is permanently available and that the processing time of each job is equal to its weight for all jobs. We develop the first polynomial-time approximation scheme (PTAS) when there is a constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, and thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; and (2) to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Next, we show that there is no fully polynomial-time approximation scheme (FPTAS) in this case unless P=NP.For the fixed job model, it has been shown that if job weights are arbitrary then there is no constant approximation for a single machine with 2 fixed jobs or for two machines with one fixed job on each machine, unless P=NP. In this paper, we assume that the weight of a job is the same as its processing time for all jobs. We show that the PTAS for the preventive model can be extended to solve this problem when the number of fixed jobs and the number of machines are both constants.     

On-line scheduling on a batch processing machine with unbounded batch size to minimize the makespan

We present on-line algorithms to minimize the makespan on a single batch processing machine. We consider a parallel batching machine that can process up to b jobs simultaneously. Jobs in the same batch complete at the same time. Such a model of a batch processing machine has been motivated by burn-in ovens in final testing stage of semiconductor manufacturing. We deal with the on-line scheduling problem when jobs arrive over time. We consider a set of independent jobs. Their number is not known in advance. Each job is available at its release date and its processing requirement is not known in advance. This general problem with infinite machine capacity is noted 1∣p − batch, r_j, b = ∞∣C_max. Deterministic algorithms that do not insert idle-times in the schedule cannot be better than 2-competitive and a simple rule based on LPT achieved this bound [Z. Liu, W. Yu, Scheduling one batch processor subject to job release dates, Discrete Applied Mathematics 105 (2000) 129–136]. If we are allowed to postpone start of jobs, the performance guarantee can be improved to 1.618. We provide a simpler proof of this best known lower bound for bounded and unbounded batch sizes. We then present deterministic algorithms that are best possible for the problem with unbounded batch size (i.e., b = ∞) and agreeable processing times (i.e., there cannot exist an on-line algorithm with a better performance guarantee). We then propose another algorithm that leads to a best possible algorithm for the general problem with unbounded batch size. This algorithm improves the best known on-line algorithm (i.e. [G. Zhang, X. Cai, C.K. Wong, On-line algorithms for minimizing makespan on batch processing machines, Naval Research Logistics 48 (2001) 241–258]) in the sense that it produces a shortest makespan while ensuring the same worst-case performance guarantee.