Unbounded parallel batch scheduling with job delivery to minimize makespan

We consider unbounded parallel batch scheduling with job delivery to minimize makespan. When the jobs have identical size, we provide a polynomial-time algorithm. When the jobs have non-identical sizes, we provide a heuristic with a worst-case performance ratio 7/4.     

Open shop scheduling problem to minimize makespan with release dates

The scheduling problem of open shop to minimize makespan with release dates is investigated in this paper. Unlike the usual researches to confirm the conjecture that the tight worst-case performance ratio of the Dense Schedule (DS) is 2 − 1/m, where m is the number of machines, the asymptotic optimality of the DS is proven when the problem scale tends to infinity. Furthermore, an on-line heuristic based on DS, Dynamic Shortest Processing Time-Dense Schedule, is presented to deal with the off-line and on-line versions of this problem. At the end of the paper, an asymptotically optimal lower bound is provided and the results of numerical experiments show the effectiveness of the heuristic.     

On-line scheduling on a batch machine to minimize makespan with limited restarts

We study the on-line scheduling on an unbounded batch machine to minimize makespan. In this model, jobs arrive over time and batches are allowed limited restarts. Any batch that contains a job which has already been restarted once cannot be restarted any more. We provide a best possible on-line algorithm for the problem with a competitive ratio .     

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.     

Scheduling jobs with release dates on parallel batch processing machines to minimize the makespan

Batch processing happens in many different industries, in which a number of jobs are processed simultaneously as a batch. In this paper we develop two heuristics for the problem of scheduling jobs with release dates on parallel batch processing machines to minimize the makespan and analyze their worst-case performance ratios. We also present a polynomial-time optimal algorithm for a special case of the problem where the jobs have equal processing times.     

The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan

We consider the problem of scheduling family jobs with release dates on a bounded batching machine to minimize the makespan. A polynomial-time approximation scheme for the identical job size model and an approximation algorithm with a worst-case ratio of for the non-identical job size model will be derived.     

Two-dedicated-machine scheduling problem with precedence relations to minimize makespan

Two-dedicated-parallel-machine scheduling problem with precedence constraints to minimize makespan is considered. This problem originally appeared as a sub-problem in assembly line balancing but it has also its own applications. Complexity and approximation results for this scheduling problem and its special cases with chains of jobs or equal-processing-times are presented.     

A single-machine scheduling problem with maintenance activities to minimize makespan

We study a single-machine scheduling problem with periodic maintenance activity under two maintenance stratagems. Although the scheduling problem with single or periodic maintenance and nonresumable jobs has been well studied, most of past studies considered only one maintenance stratagem. This research deals with a single-machine scheduling problem where the machine should be stopped for maintenance after a fixed periodic interval (T) or after a fixed number of jobs (K) have been processed. The objective is to minimize the makespan for the addressed problem. A two-stage binary integer programming (BIP) model is provided for driving the optimal solution up to 350-job instances. For the large-sized problems, two efficient heuristics are provided for the different combinations of T and K. Computational results show that the proposed algorithm Best-Fit-Butterfly (BBF) performs well because the total average percentage error is below 1%. Once the constraint of the maximum number of jobs (K) processed in the machine’s available time interval (T) is equal or larger than half of jobs, the heuristic Best-Fit-Decreasing (DBF) is strongly recommended.     

Production scheduling with supply and delivery considerations to minimize the makespan

In this paper we study a scheduling model that simultaneously considers production scheduling, material supply, and product delivery. One vehicle with limited loading capacity transports unprocessed jobs from the supplier’s warehouse to the factory in a fixed travelling time. Another capacitated vehicle travels between the factory and the customer to deliver finished jobs to the customer. The objective is to minimize the arrival time of the last delivered job to the customer. We show that the problem is NP-hard in the strong sense, and propose an O(n) time heuristic with a tight performance bound of 2. We identify some polynomially solvable cases of the problem, and develop heuristics with better performance bounds for some special cases of the problem. Computational results show that all the heuristics are effective in producing optimal or near-optimal solutions quickly.     

Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan

This paper studies the single-machine scheduling problem with deteriorating jobs and learning considerations. The objective is to minimize the makespan. We first show that the schedule produced by the largest growth rate rule is unbounded for our model, although it is an optimal solution for the scheduling problem with deteriorating jobs and no learning. We then consider three special cases of the problem, each corresponding to a specific practical scheduling scenario. Based on the derived optimal properties, we develop an optimal algorithm for each of these cases. Finally, we consider a relaxed model of the second special case, and present a heuristic and analyze its worst-case performance bound.     

工件满足一致性的同类机在线分批排序问题

研究了工件满足一致性,批容量无界的两台同类机在线分批排序问题,目标为极小化工件的最大完工时间和极小化工件的最大流程时间,三元素法分别表示为Q_2|r_ir_j?p_i≤p_j,B=∞, on-line|C_(max),Q_2|r_ir_j?p_i≥p_j,B=∞, on-line|F_(max).不失一般性,假设第一台机器速度为1,第二台机器速度为s,s≥1.对于上述两类问题设计了一个在线算法,并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α,这里α为α~2+sα-1=0的正根,特别地,当s=1时,该算法的竞争比不超过1.618.对第二类排序问题,该在线算法的竞争比不超过1+1/α.     

Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan

In this paper some discrete-continuous project scheduling problems to minimize the makespan are considered. These problems are characterized by the fact that activities of a project simultaneously require for their execution discrete and continuous resources. A class of these problems is considered where the number of discrete resources is arbitrary, and one continuous, renewable, limited resource occurs. A methodology for solving the defined problems is presented. The continuous resource allocation problem is analyzed. An exact, as well as a heuristic approach to the problem is discussed. The idea of the continuous resource discretization is described, and a special case of the problem with identical processing rate functions is analyzed. Some computational experiments for evaluating the efficiency of the proposed heuristic approaches are presented. Conclusions and directions for future research are given.     

Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan

This paper considers single machine scheduling with an aging effect in which the processing time of a job depends on its position in a sequence. It is assumed that aging ratios are job-dependent and machine can be maintained some times in a schedule. After a maintenance activity, machine will be restored to its initial condition. The processing of jobs and the maintenance activities of machine are scheduled simultaneously. The objective is to schedule the jobs and the maintenance activities, so as to minimize the makespan. We provide a polynomial time algorithm to solve the problem.     

Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan

This paper studies the bicriteria problem of scheduling n jobs on a serial-batching machine to minimize maximum cost and makespan simultaneously. A serial-batching machine is a machine that can handle up to b jobs in a batch and jobs in a batch start and complete respectively at the same time and the processing time of a batch is equal to the sum of the processing times of jobs in the batch. When a new batch starts, a constant setup time s occurs. We confine ourselves to the unbounded model, where b ≥ n. We present a polynomial-time algorithm for finding all Pareto optimal solutions of this bicriteria scheduling problem.     

List scheduling algorithms to minimize the makespan on identical parallel machines

In this paper we present constructive algorithms for the classical deterministic scheduling problem of minimizing the makespan on identical machines. Since the problem is known to beNP-hard in the strong sense, the approximate algorithms play a relevant role when solving this problem. The proposed algorithms are based on list scheduling procedures, but the assignment rule is not the same for the full set of jobs. Computational results show that these algorithms perform very well. This research has been partially supported by the Research Project H015/2000, Universidad de Alcalá. The authors are indebted to Joaquín Pérez and the referees for their helpful remarks and comments. We also wish to thank Paul Alexander Ayres for his help in the correct use of English.     

Mixed integer formulation to minimize makespan in a flow shop with batch processing machines

Batch processing machines are commonly used in wafer fabrication, kilns, and chambers used for environmental stress screening (ESS). This paper proposes two models to schedule batches of jobs on two machines in a flow shop. A set of jobs with known processing times and sizes has to be grouped, to form batches, in order to be processed on the batch processing machines. The jobs are nonidentical in size. The processing time of a batch is the longest processing time of all the jobs in that batch. Mixed integer formulations are proposed for the flow shop problem when the buffer capacity is unlimited or zero. Numerical examples are presented to demonstrate the application of our model.     

具有服务等级的两台同型机实时在线排序

考虑具有服务等级的两台同型机在线排序问题, 其中工件带有到达时间, 目标为最小化最大完工时间, 设计了竞争比为\frac{7}{4}的在线算法.