Scheduling on a Batch Processing Machine with Split Compatibility Graphs

We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only compatible jobs can be included into the same batch. This relation of compatibility is represented by a split graph. All jobs are available at the same date. The capacity of the batch processing machine is finite or infinite. The processing time of a batch is given by the processing time of the longest job in the batch. We establish the NP-hardness of the general problem and present polynomial algorithms for several special cases.     

Dynamic Scheduling on a Single Batch Processing Machine with Split Compatibility Graphs

We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only compatible jobs can be included into the same batch. This relation of compatibility is represented by a split graph. Jobs have release dates. The capacity of the batch processing machine is finite or infinite. The processing time of a batch is given by the processing time of the longest job in the batch. We establish the NP-hardness of the general problem and present polynomial algorithms for several special cases. Relating scheduling theory and graph theory appears to be an interesting and important concept.     

极小化总完工时间的同时加工排序

讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况.     

极小化最大完工时间的单机分批加工问题

本文考虑极小化最大完工时间的单机分批加工问题．设有n个工件和一台批加工机器．每个工件有一个释放时间和一个加工时间．批加工机器可以同时加工b(b相似文献   

ON-LINE PROBLEMS OF MINIMIZING MAKESPAN ON A SINGLE BATCH PROCESSING MACHINE WITH NONIDENTICAL JOB SIZES

The on-line problem of scheduling on a batch processing machine with nonidentical job sizes to minimize makespan is considered. The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is given by the longest processing time of any job in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time becomes known upon its arrival. The paper deals with two variants： the case only with two distinct arrival times and the general case. For the first case, an on-line algorithm with competitive ratio 119/44 is given. For the latter one, a simple algorithm with competitive ratio 3 is given. For both variants the better ratios can be obtained if the problem satisfies proportional assumption.     

Optimal methods for batch processing problem with makespan and maximum lateness objectives

In this paper we consider the problem of scheduling n jobs on a single batch processing machine in which jobs are ordered by two customers. Jobs belonging to different customers are processed based on their individual criteria. The considered criteria are minimizing makespan and maximum lateness. A batching machine is able to process up to b jobs simultaneously. The processing time of each batch is equal to the longest processing time of jobs in the batch. This kind of batch processing is called parallel batch processing. Optimal methods for three cases are developed: unbounded batch capacity, b > n, with compatible job groups and bounded batch capacity, b  n, with compatible and non compatible job groups. Each job group represents a different class of customers and the concept of being compatible means that jobs which are ordered by different customers are allowed to be processed in a same batch. We propose an optimal method for the problem with incompatible groups and unbounded batches. About the case when groups are incompatible and bounded batches, our proposed method is considered as optimal when the group with maximum lateness objective has identical processing times. We regard this method, however, as a heuristic when these processing times are different. When groups are compatible and batches are bounded we consider another problem by assuming the same processing times for the group which has the maximum lateness objective and propose an optimal method for this problem.     

工件具有任意尺寸的混合分批平行机排序问题的近似算法

本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中, 一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸, 每台机器可以同时处理多个工件, 称为一个批, 只要这些工件尺寸之和不超过其容量; 一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和; 目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形, 为强NP-困难的。对此给出了一个$\left( {2 + 2\alpha+\alpha^{2}}\right)$-近似算法, 其中$\alpha$为给定的权重参数, 满足$0\leq\alpha\leq 1$。     

具有线性恶化效应的在线分批排序问题

本文研究一类具有线性恶化效应的单机在线分批排序问题,工件$J_j$的加工时间为$p_j=b_j+\alpha t$, 其中$b_j$为基本加工时间, $\alpha>0$为恶化率, $t$是开工时间. 工件的到达时间是未知的, 工件的基本加工时间只有在工件到达之后才能知道.多个工件可以作为一批被机器同时加工, 批的加工时间为该批中工件最大加工时间.本文对于目标为极小化makespan的批容量无限的单机问题给出一个在线算法$\beta H^\infty$,并证明其竞争比和问题的下界相同, 进而算法是最优的.     

Batch processing with interval graph compatibilities between tasks

We analyze batch-scheduling problems that arise in connection with certain industrial applications. The models concern processing on a single max-batch machine with the additional feature that the tasks of the same batch have to be compatible. Compatibility is a symmetric binary relation—the compatible pairs are described with an undirected “compatibility graph”, which is often an interval graph according to some natural practical conditions that we present. We consider several models with varying batch capacities, processing times or compatibility graphs. We summarize known results, and present a min-max formula and polynomial time algorithms.     

Minimizing number of tardy jobs on a batch processing machine with incompatible job families

In this paper we consider the problem of minimizing number of tardy jobs on a single batch processing machine. The batch processing machine is capable of processing up to B jobs simultaneously as a batch. We are given a set of n jobs which can be partitioned into m incompatible families such that the processing times of all jobs belonging to the same family are equal and jobs of different families cannot be processed together. We show that this problem is NP-hard and present a dynamic programming algorithm which has polynomial time complexity when the number of job families and the batch machine capacity are fixed. We also show that when the jobs of a family have a common due date the problem can be solved by a pseudo-polynomial time procedure.     

提前预知信息的在线分批排序问题

研究工件可提前预知信息的在线分批排序问题, 工件的预知信息时间依时间到达, 目标为极小化最大完工时间. 已知从工件的信息可预知到该工件可加工需要时间~$a$, 所有工件的最大加工时间为~$p_{{\rm max}}$, 多个工件可以作为一批被机器同时加工, 批的加工时间为该批工件中最长加工时间. 对于批容量无限的单机问题给出一个在线算法~$\gamma H^\infty$, 并证明其竞争比和问题的下界都为~$1+\gamma$, 其中~$\gamma=\left(-1+\sqrt{1+\frac{4p_{{\rm max}}}{p_{{\rm max}}+a}}\right)/2$, 进而算法是最优的.     

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

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

Scheduling a single machine with multiple job processing ability to minimize makespan

This paper investigates a new problem, called single machine scheduling with multiple job processing ability, which is derived from the production of the continuous walking beaming reheating furnace in iron and steel industry. In this problem, there is no batch and the jobs enter and leave the machine one by one and continuously, which is different from general single machine batch scheduling problem where the jobs in a batch share the same start and departure time. Therefore, the start time and the departure time of a job depend on not only the job sequence but also the machine capacity. This problem is also different from the single semi-continuous batching machine scheduling recently studied in the literature, where the jobs are processed in batch mode and a new batch cannot be started for processing until the processing of the previous batch is completed though jobs in the same batch enter and leave the machine one by one. The objective of this problem is to minimize the makespan. We formulate this problem as a mixed integer linear programming model and propose a particle swarm optimization (PSO) algorithm for this problem. Computational results on randomly generated instances show that the proposed PSO algorithm is effective.     

求带释放时间的半导体煅烧排序的最短交付时间的一个高效PTAS

本文研究一个目标是最小化最大交付时间的能分批处理的非中断单机排序问题．这个问题来源于半导体制造过程中对芯片煅烧工序的排序．煅烧炉可以看成一个能同时最多加工B（〈n）个工件的处理机．此外，每个工件有一个可以允许其加工的释放时间和一个完成加工后的额外交付时间．该问题就是将工件分批后再依批次的排序加工，使得所有工件都交付后所需的时间最短．我们设计了一个用时O（f（l／ε）n^5/2）的多项式时间近似方案，其中关于1／ε的指数函数厂（1／ε）对固定的ε是个常数.     

Single machine unbounded parallel-batch scheduling with forbidden intervals

In this paper we consider the single machine parallel-batch scheduling with forbidden intervals. There are some forbidden intervals in which the machine cannot be available. The jobs are processed in batches form in the remaining free time-slots without preemption, where the processing time of a batch is defined to be the maximum processing time of the jobs in this batch. We show that, when the objective is bottleneck form, maximum lateness, or makespan with release dates of jobs, the considered problem can be solved in polynomial time.     

带有分批费用的容量有界的单机平行分批排序问题

考虑的问题是在添加工资费用或包装费用等附加的分批费用下,如何使单机平行分批中总完工时间和分批费用之和达到最小.首先我们假定工件和批处理机都在零时刻到达,工件被成批地进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用.然后对具有m个不同的加工时间,批容量有界且为固定值b的情形下目标函数为∑C_j与分批费用之和这一排序问题,利用动态规划的方法给出了多项式时间算法,时间界为O(b²m2m²222^m).     

Single machine batch scheduling to minimize the weighted number of late jobs

The single machine batch scheduling problem to minimize the weighted number of late jobs is studied. In this problem,n jobs have to be processed on a single machine. Each job has a processing time, a due date and a weight. Jobs may be combined to form batches containing contiguously scheduled jobs. For each batch, a constant set-up time is needed before the first job of this batch is processed. The completion time of each job in the batch coincides with the completion time of the last job in this batch. A job is late if it is completed after its due date. A schedule specifies the sequence of jobs and the size of each batch, i.e. the number of jobs it contains. The objective is to find a schedule which minimizes the weighted number of late jobs. This problem isNP-hard even if all due dates are equal. For the general case, we present a dynamic programming algorithm which solves the problem with equal weights inO(n ³) time. We formulate a certain scaled problem and show that our dynamic programming algorithm applied to this scaled problem provides a fully polynomial approximation scheme for the original problem. Each algorithm of this scheme has a time requirement ofO(n ³/ +n ³ logn). A side result is anO(n logn) algorithm for the problem of minimizing the maximum weight of late jobs.Supported by INTAS Project 93-257.     

The coordination of transportation and batching scheduling

We study a coordinated scheduling problem of production and transportation in which each job is transported to a single batching machine for further processing. There are m vehicles that transport jobs from the holding area to the batching machine. Each vehicle can transport only one job at a time. The batching machine can process a batch of jobs simultaneously where there is an upper limit on the batch size. Each batch to be processed occurs a processing cost. The problem is to find a joint schedule of production and transportation such that the sum of the total completion time and the total processing cost is optimized. For a special case of the problem where the job assignment to the vehicles is predetermined, we provide a polynomial time algorithm. For the general problem, we prove that it is NP-hard (in the ordinary sense) and present a pseudo-polynomial time algorithm. A fully polynomial time approximation scheme for the general problem is obtained by converting an especially designed pseudo-polynomial dynamic programming algorithm.     

具有前瞻区间的两个工件组单机在线排序问题

研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化最大完工时间. 在无界平行分批排序中, 一台容量无限制机器可将多个工件形成一批同时加工, 每一批的加工时间等于该批中最长工件的加工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta]内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能安排在同一批中加工.对该问题提供了一个竞争比为\ 1+\alpha 的最好可能的在线算法,其中\ \alpha 是方程2\alpha^{2}+(\beta +1)\alpha +\beta -2=0的一个正根, 这里0\leq \beta <1.