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.     

Stochastic cyclic scheduling problem in synchronous assembly and production lines

In this paper we address the stochastic cyclic scheduling problem in synchronous assembly and production lines. Synchronous lines are widely used in the production and assembly of various goods such as automobiles or household appliances. We consider cycle time minimisation (or throughput rate maximisation) as the objective of the scheduling problem with the assumption that the processing times are independent random variables. We first discuss the two-station case and present a lower bounding scheme and an approximate solution procedure for the scheduling problem. For the general case of the problem, two heuristic solution procedures are presented. An extension of the two-station lower bound to the general case of the problem is also discussed. The performance of the proposed heuristics on randomly generated problems is documented, and the impact of scheduling decisions on problems with different levels of variability in processing times are analysed. We also analyse the problem of sequence determination when the available information is limited to the expected values of individual processing times.     

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.     

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

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

Integrated scheduling of production and distribution for manufacturers with parallel batching facilities

We consider a class of integrated scheduling problems for manufacturers. The manufacturer processes job orders and delivers products to the customer. The objective is to minimize the service span, that is, the period lasting from the time when the order is received to the time when all the products have been delivered to the customer. In the production phase, parallel batch-processing facilities are used to process the jobs. Jobs have arbitrary sizes and processing times. Each facility has a fixed capacity and jobs are processed in batches with the restriction that the total size of jobs in a batch does not exceed the facility capacity. When all the jobs in a batch are completed, the batch is completed. In the distribution phase, the manufacturer uses a vehicle with a fixed capacity to deliver products. The transportation time from the manufacturer to the customer is a constant. Completed products can be delivered in one transfer if the total size does not exceed the vehicle capacity. We first consider the problem where jobs have the same size and arbitrary processing times. We propose approximation algorithms for the problem and we show that a worst-case ratio performance guarantee is respectively 2–1/m. Then we consider the problem where jobs have the same processing time and arbitrary sizes. An approximation algorithm is proposed with an absolute worst-case ratio of 13/7 and an asymptotic worst-case ratio of 11/9. Both the proposed algorithms can be executed in polynomial time.     

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

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

The interface of buffer design and cyclic scheduling decisions in deterministic flow lines

In this paper, we address some issues on the interface of buffer design and cyclic scheduling decisions in a multi-product deterministic flow line. We demonstrate the importance of the above interface for the throughput performance of the flow line. In particular, we point out that the use of sequence-independent information, such as workload distribution and variability in processing times among stations, is not adequate to decide the optimal buffer configuration of the flow line. We formulate the buffer design problem for a fixed sequence of jobs as a general resource allocation problem, and suggest two effective heuristics for its solution. For the simultaneous buffer design and cyclic scheduling problem, we suggest an iterative scheme that builds on the effectiveness of the above heuristics. One of the side results of our extensive computational studies on this problem is that the general guidelines of buffer design in single-product flow lines with stochastic processing times are not directly transferable to the multiproduct deterministic flow line environment.     

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.     

并行分批排序综述

并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。     

具有两个不相容工件族单位工件的有界分批在线排序问题

研究具有两个不相容工件族单位工件单机有界平行分批的在线排序问题.工件按时在线到达,目标是最小化最大完工时间.在有界平行分批排序中,容量有限制机器最多可将b个工件形成一批同时加工,每个工件及每一批的加工时间为1.不相容工件族是指来自不同工件组的工件不能放在同一批加工.对该问题提供了一个竞争比为√17+3/4的最好可能的在线算法.     

Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times

In many realistic scheduling settings a job processed later consumes more time than the same job processed earlier – this is known as scheduling with deteriorating jobs. Most research on scheduling with deteriorating jobs assumes that the actual processing time of a job is an increasing function of its starting time. Thus a job processed late may incur an excessively long processing time. On the other hand, setup times occur in manufacturing situations where jobs are processed in batches whereby each batch incurs a setup time. This paper considers scheduling with deteriorating jobs in which the actual processing time of a job is a function of the logarithm of the total processing time of the jobs processed before it (to avoid the unrealistic situation where the jobs scheduled late will incur excessively long processing times) and the setup times are proportional to the actual processing times of the already scheduled jobs. Under the proposed model, we provide optimal solutions for some single-machine problems.     

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.     

Minimizing makespan on a single burn-in oven in semiconductor manufacturing

This paper considers a scheduling problem for a single burn-in oven in semiconductor manufacturing industry where the oven is a batch processing machine and each batch processing time is represented by the largest processing time among those of all the jobs contained in the batch. The objective measure of the problem is the maximum completion time (makespan) of all jobs. This paper investigates a static case in which all jobs are available to process at time zero, and also analyzes a dynamic case with different job-release times, for which a branch-and-bound algorithm and several heuristics are exploited. The worst case error performance ratios of the heuristics are also derived.     

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

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

Realistic two-stage flowshop batch scheduling problems with transportation capacity and times

This paper investigates single-batch and batch-single flow shop scheduling problem taking transportation among machines into account. Both transportation capacity and transportation times are explicitly considered. While the single processing machine processes one job at a time, the batch processing machine processes a batch of jobs simultaneously. The batch processing time is the longest processing times of jobs assigned to that batch.Each problem is formulated as a mixed integer programming model to find optimal makespan. Lower bounds and heuristic algorithms are proposed and computational experiments are carried out to verify their effectiveness.     

Markovian analysis for performance evaluation and scheduling in m machine stochastic flow-shop with buffers of any capacity

This paper deals with performance evaluation and scheduling in m machine static stochastic permutation flow-shop with buffers of any capacity (unlimited, limited or null). The processing time of a given job for a given machine is assumed to be exponentially distributed with a known rate. We propose a theorem which provides recursive scheme based on Markov chains and Chapman–Kolmogorov equations to compute the expected completion time of the last job for any sequence of jobs. This scheme is combined with metaheuristics based on simulated annealing for the scheduling problem. Computational results are given.     

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.     

An iterative approach for the serial batching problem with parallel machines and job families

In this paper, we consider a parallel machine scheduling problem to minimize the total completion time. Each job belongs to a certain family. All jobs of one family have identical processing times. Major setups occur between jobs of different families, and we include sequence dependencies. Batches of jobs belonging to the same family can be formed to avoid these setups. Furthermore, we assume serial batching and batch availability. Therefore, the processing time of a batch is the sum of the processing times of all jobs grouped into the corresponding batch. An iterative method is developed for solving this specific problem. This approach alternates between varying batch sizes using an efficient heuristic and sequencing batches based on variable neighborhood search (VNS). Computational results demonstrate that the iterative heuristic outperforms heuristics based on a fixed batch size and list scheduling.     

On scheduling an unbounded batch machine

A batch machine is a machine that can process up to c jobs simultaneously as a batch, and the processing time of the batch is equal to the longest processing time of the jobs assigned to it. In this paper, we deal with the complexity of scheduling an unbounded batch machine, i.e., c=+∞. We prove that minimizing total tardiness is binary NP-hard, which has been an open problem in the literature. Also, we establish the pseudopolynomial solvability of the unbounded batch machine scheduling problem with job release dates and any regular objective. This is distinct from the bounded batch machine and the classical single machine scheduling problems, most of which with different release dates are unary NP-hard. Combined with the existing results, this paper provides a nearly complete mapping of the complexity of scheduling an unbounded batch machine.     

A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size

In this paper, we propose different heuristic algorithms for flow shop scheduling problems, where the jobs are partitioned into groups or families. Jobs of the same group can be processed together in a batch but the maximal number of jobs in a batch is limited. A setup is necessary before starting the processing of a batch, where the setup time depends on the group of the jobs. In this paper, we consider the case when the processing time of a batch is given by the maximum of the processing times of the operations contained in the batch. As objective function we consider the makespan as well as the weighted sum of completion times of the jobs. For these problems, we propose and compare various constructive and iterative algorithms. We derive suitable neighbourhood structures for such problems with batch setup times and describe iterative algorithms that are based on different types of local search algorithms. Except for standard metaheuristics, we also apply multilevel procedures which use different neighbourhoods within the search. The algorithms developed have been tested in detail on a large collection of problems with up to 120 jobs.