Online Over Time Scheduling on Parallel-Batch Machines: A Survey
---
paper_title: A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor

paper_content:

In this paper, we present a literature review, classification schemes and a simple meta-analysis for scheduling of batch processors (SBP) research in semiconductor manufacturing (SM). This review is based on a study of journals and web-based documents/articles, which include conference materials, lecture notes in computer science, working papers, etc. There are 98 articles published in various publication outlets between 1986 and October 2004. Based on the literature review carried out and the nature of SBP research observed in SM, we have introduced two classification schemes to systematically organize the published articles. The first classification scheme is based on the problem configurations of SBP research in SM and the second one is based on the solution methodology followed by the researchers. These classification schemes indicate that there is much research scope on SBP research in SM. Furthermore, a simple meta-analysis is carried out to enhance understanding on the development and evolution of SBP research in SM and to identify potential research areas for further research and for improvement. The results show that there is an increasing trend in SBP research in SM. A comprehensive list of references is presented. This study is expected to provide a source of reference for other researchers (or readers), who are interested in SBP research particularly in SM and help stimulate further interest.
---
paper_title: Sequencing and scheduling : algorithms and complexity

paper_content:

Sequencing and scheduling as a research area is motivated by questions that arise in production planning, in computer control, and generally in all situations in which scarce resources have to be allocated to activities over time. In this survey, we concentrate on the area of deterministic machine scheduling. We review complexity results and optimization and approximation algorithms for problems involving a single machine, parallel machines, open shops, flow shops and job shops. We also pay attention to two extensions of this area: resource-constrained project scheduling and stochastic machine scheduling.
---
paper_title: A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine

paper_content:

We consider a single-machine on-line scheduling problem where jobs arrive over time. A set of independent jobs has to be scheduled on the machine, where preemption is not allowed and the number of jobs is unknown in advance. Each job becomes available at its release date, which is not known in advance, and its characteristics, i.e., processing requirement and delivery time, become known at its arrival. The objective is to minimize the time by which all jobs have been delivered. We propose and analyze an on-line algorithm based on the following idea: As soon as the machine becomes available for processing, choose an available job with highest priority, and schedule it if its processing requirement is not too large. Otherwise, postpone the start of this job. We prove that our algorithm has performance bound $(\sqrt{5}+1)/2 \approx 1.61803$, and we show that there cannot exist a deterministic on-line algorithm with a better performance ratio for this problem.
---
paper_title: Optimal on-Line Algorithms for Single-Machine Scheduling

paper_content:

We consider single-machine on-line scheduling problems where jobs arrive over time. A set of independent jobs has to be scheduled on the machine, where preemption is not allowed and the number of jobs is unknown in advance. Each job becomes available at its release date, which is not known in advance, and its characteristics, e.g., processing requirement, become known at its arrival. We deal with two problems: minimizing total completion time and minimizing the maximum time by which all jobs have been delivered. For both problems we propose and analyze an on-line algorithm based on the following idea: As soon as the machine becomes available for processing, choose an available job with highest priority, and schedule it if its processing requirement is not too large. Otherwise, postpone the start of this job for a while. We prove that our algorithms have performance bound 2 and (√5 + 1)/2, respectively, and we show that for both problems there cannot exist an on-line algorithm with a better performance guarantee.
---
paper_title: Semi-online scheduling with decreasing job sizes

paper_content:

We investigate the problem of semi-online scheduling jobs on m identical parallel machines where the jobs arrive in order of decreasing sizes. We present a complete solution for the preemptive variant of semi-online scheduling with decreasing job sizes. We give matching lower and upper bounds on the competitive ratio for any fixed number m of machines; these bounds tend to (1+3)/2~1.36603, as the number of machines goes to infinity. Our results are also the best possible for randomized algorithms. For the non-preemptive variant of semi-online scheduling with decreasing job sizes, a result of Graham (SIAM J. Appl. Math. 17 (1969) 263-269) yields a (4/3-1/(3m))-competitive deterministic non-preemptive algorithm. For m=2 machines, we prove that this algorithm is the best possible (it is 7/6-competitive). For m=3 machines we give a lower bound of (1+37)/6~1.18046. Finally, we present a randomized non-preemptive 8/7-competitive algorithm for m=2 machines and prove that this is optimal.
---
paper_title: Scheduling one batch processor subject to job release dates

paper_content:

In this paper, we consider the problem of scheduling jobs with release dates on a single-batch processor in order to minimize the makespan. This problem is proved to be NP-hard even for the case with two distinct release dates. Then a pseudopolynomial algorithm is presented for the case with a fixed number of release dates. Finally, a greedy heuristic for the general problem is shown to have the best-performance bound 2.
---
paper_title: Online Scheduling with Known Arrival Times

paper_content:

We consider an online scheduling environment where decisions are made without knowledge of the data of jobs that may arrive later. However, additional jobs can only arrive at known future times. This environment interpolates between the classical offline and online scheduling environments and approaches the classical online environment when there are many equally spaced potential job arrival times. The objective is to minimize the sum of weighted completion times, a widely used measure of work-in-process inventory cost and customer service. For a nonpreemptive single machine environment, we show that a lower bound on the competitive ratio of any online algorithm is the solution of a mathematical program. This lower bound is between (1 + SQRT(5))/2 and 2, with the exact value depending on the potential job arrival times. We also provide a “best possible” online scheduling algorithm and show that its competitive ratio matches this lower bound. We analyze two practically motivated special cases where the potential job arrival times have a special structure. When there are many equally spaced potential job arrival times, the competitive ratio of our online algorithm approaches the best possible competitive ratio of 2 for the classical online problem.
---
paper_title: Minimizing Makespan on a Single Batch Processing Machine with Dynamic Job Arrivals

paper_content:

We consider the problem of minimizing makespan Cmax on a single batch processing machine in the presence of dynamic job arrivals. The batch processing machine can process up to B jobs simultaneously. The processing time of a batch is given by the processing time of the longest job in the batch. We present polynomial and pseudopolynomial-time algorithms for several special cases, develop efficient heuristics for the general problem and evaluate their performance through extensive computational experiments. Our results indicate that several of the heuristics have an excellent average performance with a modest computational burden.
---
paper_title: Semi-on-line problems on two identical machines with combined partial information

paper_content:

This paper considers the semi-on-line versions of scheduling problem P2||C"m"a"x. We study the semi-on-line problems with combination of two types of information. Five basic types of partial information are considered. For two kinds of pairwise combination, we present their respective optimal semi-on-line algorithms which show that combination can admit to construct better algorithms.
---
paper_title: A REVIEW OF PRODUCTION PLANNING AND SCHEDULING MODELS IN THE SEMICONDUCTOR INDUSTRY PART I: SYSTEM CHARACTERISTICS, PERFORMANCE EVALUATION AND PRODUCTION PLANNING

paper_content:

Although the national importance of the semiconductor industry is widely acknowledged, it is only recently that the production planning and scheduling problems encountered in this environment have begun to be addressed using industrial engineering and operations research.techniques. These problems have several features that make them difficult and challenging: random yields and rework, complex product flows, and rapidly changing products and technologies. Hence their solution will contribute considerably to die theory and practice of production planning and control. In a two-part project we present a review of research in this area to date, discuss the applicability of the various approaches and suggest directions for future research. In this paper, Part I, we describe the characteristics of the semiconductor manufacturing environment and review models related to performance evaluation and production planning. Part II will review research on shop-floor control in this industry to date.
---
paper_title: Semi-on-line multiprocessor scheduling with given total processing time

paper_content:

We are given a set of identical machines and a sequence of jobs, the sum of whose weights is known in advance. The jobs are to be assigned on-line to one of the machines and the objective is to minimize the makespan. An algorithm with performance ratio 1.6 and a lower bound of 1.5 is presented. These results improve on the recent results by Azar and Regev, who proposed an algorithm with performance ratio 1.625 for the less general problem that the optimal makespan is known in advance.
---
paper_title: On-line scheduling of a single machine to minimize total weighted completion time

paper_content:

This paper considers the on-line scheduling of a single machine in which jobs arrive over time, and preemption is not allowed. The goal is to minimize the total weighted completion time. We show that a simple modification of the shortest weighted processing time rule has a competitive ratio of 2. This result is established using a new proof technique which does not rely explicitly on a lower bound on the optimal objective function value. Since it is known that no on-line algorithm can have a competitive ratio of less than 2, we have resolved the open issue of determining the minimum competitive ratio for this problem.
---
paper_title: Scheduling A Batching Machine

paper_content:

We address the problem of scheduling n jobs on a batching machine to minimize regular scheduling criteria that are non-decreasing in the job completion times. A batching machine is a machine that can handle up to b jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is equal to the largest processing time of any job in the batch. We analyse two variants: the unbounded model, where b⩾n; and the bounded model, where b<n. ::: ::: ::: ::: For the unbounded model, we give a characterization of a class of optimal schedules, which leads to a generic dynamic programming algorithm that solves the problem of minimizing an arbitrary regular cost function in pseudopolynomial time. The characterization leads to more efficient dynamic programming algorithms for specific cost functions: a polynomial algorithm for minimizing the maximum cost, an O(n3) time algorithm for minimizing the number of tardy jobs, an O(n2) time algorithm for minimizing the maximum lateness, and an O(n log n) time algorithm for minimizing the total weighted completion time. Furthermore, we prove that minimizing the weighted number of tardy jobs and the total weighted tardiness are NP-hard problems. ::: ::: ::: ::: For the bounded model, we derive an O(nb(b−1)) time dynamic programming algorithm for minimizing total completion time when b>1; for the case with m different processing times, we give a dynamic programming algorithm that requires O(b2m22m) time. Moreover, we prove that due date based scheduling criteria give rise to NP-hard problems. Finally, we show that an arbitrary regular cost function can be minimized in polynomial time for a fixed number of batches. © 1998 John Wiley & Sons, Ltd.
---
paper_title: CONTROL OF A BATCH-PROCESSING MACHINE : A COMPUTATIONAL APPROACH

paper_content:

Batch processing machines, where a number of jobs are processed simultaneously as a batch, occur frequently in semiconductor manufacturing environments, particularly at diffusion in wafer fabrication and at burn-in in final test. In this paper we consider a batch-processing machine subject to uncertain (Poisson) job arrivals. Two different cases are studied: (1) the processing times of batches are independent and identically distributed (IID), corresponding to a diffusion tube; and (2) the processing time of each batch is the maximum of the processing times of its constituent jobs, where the processing times of jobs are IID, modelling a burn-in oven. We develop computational procedures to minimize the expected long-run-average number of jobs in the system under a particular family of control policies. The control policies considered are threshold policies, where processing of a batch is initiated once a certain number of jobs have accumulated in the system. We present numerical examples of our methods and...
---
paper_title: Scheduling Algorithms

paper_content:

Besides scheduling problems for single and parallel machines and shop scheduling problems, this book covers advanced models involving due-dates, sequence dependent changeover times and batching. Discussion also extends to multiprocessor task scheduling and problems with multi-purpose machines. Among the methods used to solve these problems are linear programming, dynamic programming, branch-and-bound algorithms, and local search heuristics. The text goes on to summarize complexity results for different classes of deterministic scheduling problems.
---
paper_title: Minimizing Makespan in Batch Machine Scheduling

paper_content:

We study the scheduling of a set of n jobs, each characterized by a release (arrival) time and a processing time, for a batch processing machine capable of running at most B jobs at a time. We obtain an O(n log n)-time algorithm when B is unbounded. When there are only m distinct release times and the inputs are integers, we obtain an O(n(BRmax)m-1 (2/m)m-3)-time algorithm where Rmax is the difference between the maximum and minimum release times. When there are k distinct processing times and m release times, we obtain an O(kk+2 Bk+1 m2 log m)-time algorithm. We obtain even better algorithms for m = 2 and for k = 1. These algorithms improve most of the corresponding previous algorithms for the respective special cases and lead to improved approximation schemes for the general problem.
---
paper_title: Efficient algorithms for scheduling semiconductor burn-in operations

paper_content:

In this paper, we study the problem of scheduling semiconductor burn-in operations, where burn-in ovens are modeled as batch processing machines. A batch processing machine is one that can process up to B jobs simultaneously. The processing time of a batch is equal to the largest processing time among all jobs in the batch. We present efficient dynamic programming-based algorithms for minimizing a number of different performance measures on a single batch processing machine. We also present heuristics for a number of problems concerning parallel identical batch processing machines and we provide worst case error bounds.
---
paper_title: Approximation Algorithms in Batch Processing

paper_content:

AbstractA polynomial approximation scheme for minimizing makespan in a batch processing system under dynamic job arrivals is presented. A lower bound of ::: $${{(\sqrt 5 + 2)} \mathord{\left/ {\vphantom {{(\sqrt 5 + 2)} 2}} \right. \kern-\nulldelimiterspace} 2}$$ ::: on the competitive ratio of any on-line algorithm is proved. This is matched by an on-line algorithm for the special case of unbounded machine capacity.
---
paper_title: On‐line algorithms for minimizing makespan on batch processing machines

paper_content:

We consider problem of scheduling jobs on-line on batch processing machines with dynamic job arrivals to minimize makespan. A batch machine can handle up to B jobs simultaneously. The jobs that are processed together from a batch, and all jobs in a batch start and complete at the same time. 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. In the first part of this paper, we address the single batch processing machine scheduling problem. First we deal with two variants: the unbounded model where B is sufficiently large and the bounded model where jobs have two distinct arrival times. For both variants, we provide on-line algorithms with worst-case ratio (the inverse of the Golden ratio) and prove that these results are the best possible. Furthermore, we generalize our algorithms to the general case and show a worst-case ratio of 2. We then consider the unbounded case for parallel batch processing machine scheduling. Lower bound are given, and two on-line algorithms are presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 241–258, 2001
---
paper_title: On-line scheduling on a batch machine to minimize makespan with limited restarts

paper_content:

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 32.
---
paper_title: A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine

paper_content:

We consider a single-machine on-line scheduling problem where jobs arrive over time. A set of independent jobs has to be scheduled on the machine, where preemption is not allowed and the number of jobs is unknown in advance. Each job becomes available at its release date, which is not known in advance, and its characteristics, i.e., processing requirement and delivery time, become known at its arrival. The objective is to minimize the time by which all jobs have been delivered. We propose and analyze an on-line algorithm based on the following idea: As soon as the machine becomes available for processing, choose an available job with highest priority, and schedule it if its processing requirement is not too large. Otherwise, postpone the start of this job. We prove that our algorithm has performance bound $(\sqrt{5}+1)/2 \approx 1.61803$, and we show that there cannot exist a deterministic on-line algorithm with a better performance ratio for this problem.
---
paper_title: A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times

paper_content:

We consider a single batch machine on-line scheduling problem with delivery times. In this paper on-line means that jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Once the processing of a job is completed it is delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job J j , its processing time and delivery time are denoted by p j and q j , respectively. We consider two restricted models: (1) the jobs have small delivery times, i.e., for each job J j , q j ≤p j ; (2) the jobs have agreeable processing and delivery times, i.e., for any two jobs J i and J j , p i >p j implies q i ≥q j . We provide an on-line algorithm with competitive ratio \((\sqrt{5}+1)/2\) for both problems, and the results are the best possible.
---
paper_title: A Flexible On-line Scheduling Algorithm for Batch Machine with Infinite Capacity

paper_content:

We study on-line scheduling on a batch machine with infinite capacity. We present a flexible on-line scheduling algorithm that aims at minimizing the makespan and achieves the optimal competitive ratio of $(1+\sqrt{5})/2$ . Copyright Springer Science + Business Media, Inc. 2005
---
paper_title: The single-machine parallel-batching on-line scheduling problem with family jobs to minimize makespan

paper_content:

Abstract In this paper we consider the single-machine parallel-batching scheduling problem with family jobs under on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job until its arrival. Our objective is to minimize the maximum completion time of the jobs (makespan). We deal with two variants of the problem: the unbounded model in which the machine can handle infinite number of jobs simultaneously and the bounded model. For the unbounded case, we provide an on-line algorithm with a worst-case ratio of 2 and prove that there exists no on-line algorithm with a worst-case ratio less than 2. For the bounded case, we also present an on-line algorithm with a worst-case ratio of 2.
---
paper_title: Scheduling one batch processor subject to job release dates

paper_content:

In this paper, we consider the problem of scheduling jobs with release dates on a single-batch processor in order to minimize the makespan. This problem is proved to be NP-hard even for the case with two distinct release dates. Then a pseudopolynomial algorithm is presented for the case with a fixed number of release dates. Finally, a greedy heuristic for the general problem is shown to have the best-performance bound 2.
---
paper_title: Minimizing Makespan on a Single Batch Processing Machine with Dynamic Job Arrivals

paper_content:

We consider the problem of minimizing makespan Cmax on a single batch processing machine in the presence of dynamic job arrivals. The batch processing machine can process up to B jobs simultaneously. The processing time of a batch is given by the processing time of the longest job in the batch. We present polynomial and pseudopolynomial-time algorithms for several special cases, develop efficient heuristics for the general problem and evaluate their performance through extensive computational experiments. Our results indicate that several of the heuristics have an excellent average performance with a modest computational burden.
---
paper_title: Best semi-online algorithms for unbounded parallel batch scheduling

paper_content:

We consider semi-online scheduling of an unbounded parallel batch machine to minimize the makespan where, at the present time instant t, information on the first longest job arriving after t is known. In this paper online means that jobs arrive over time, J^*(t) denotes the first longest job arriving after t, and p^*(t) and r^*(t) denote the processing time and arrival time of J^*(t), respectively. Given information p^*(t), we present an online algorithm with a competitive ratio (5-5)/2~1.382, and show that the algorithm is the best possible; furthermore, this algorithm generates at most two batches. This algorithm is also the best possible given information J^*(t). Given information r^*(t), we present an online algorithm with a competitive ratio 3/2, and show that any online algorithm cannot have a competitive ratio less than 33~1.442; furthermore, this algorithm generates at most three batches. Given information r^*(t) with the restriction that an online algorithm generates at most two batches, we present an online algorithm with a competitive ratio (5+1)/2~1.618, and show that the algorithm is the best possible.
---
paper_title: Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart

paper_content:

Abstract We consider the online (over time) scheduling of equal length jobs on a bounded parallel batch machine with a capacity b to minimize makespan with restart or limited restart. Let α ≈ 0.29 , β ≈ 0.47 , γ ≈ 0.38 , and φ ≈ 0.40 be four parameters defined in the text. When b = 2 , we present a best possible online algorithm H L ( b = 2 ) with a competitive ratio of 1 + α under the assumption of restart or limited restart. Under the assumption of limited restart with b ≥ 3 , we present a best possible online algorithm H L ( b ≥ 3 ) with a competitive ratio of 1 + β . Under the assumption of restart, when b = 3 , we present a best possible online algorithm H ( b = 3 ) with a competitive ratio of 1 + γ , and when b ≥ 4 , we present a best possible online algorithm H ( b ≥ 4 ) with a competitive ratio of 1 + φ . In our online algorithms under the assumption of restart, each job is interrupted at most two times. Consequently, our results cover the setting of k -limited restart for all k ≥ 1 .
---
paper_title: Optimal on-line algorithms for one batch machine with grouped processing times

paper_content:

In this paper, we study on-line scheduling problems on a batch machine with the assumption that all jobs have their processing times in [p, (1+?)p], where p>0 and $\phi=(\sqrt{5}-1)/2$ . Jobs arrive over time. First, we deal with the on-line problem on a bounded batch machine with the objective to minimize makespan. A class of algorithms with competitive ratio $(\sqrt{5}+1)/2$ are given. Then we consider the scheduling on an unbounded batch machine to minimize the time by which all jobs have been delivered, and provide a class of on-line algorithms with competitive ratio $(\sqrt{5}+1)/2$ . The two class of algorithms are optimal for the problems studied here.
---
paper_title: A best online algorithm for scheduling on two parallel batch machines

paper_content:

We consider the online scheduling on two parallel batch machines with infinite batch size to minimize makespan, where jobs arrive over time. That is, all information of a job is not available until it is released. For this online scheduling problem, Nong et al. [Q.Q. Nong, T.C.E. Cheng, C.T. Ng, An improved online algorithm for scheduling on two unrestrictive parallel batch processing machines, Operations Research Letters, 36 (2008) 584-588] have provided an online algorithm with competitive ratio no greater than 2. We show that this bound is tight for the problem. Furthermore we give a new best possible online algorithm with a tighter structure.
---
paper_title: A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines

paper_content:

We study on-line scheduling on parallel batch machines. Jobs arrive over time. A batch processing machine can handle up to B jobs simultaneously. The jobs that are processed together form a batch and all jobs in a batch start and are completed at the same time. The processing time of a batch is given by the processing time of the longest job in the batch. The objective is to minimize the makespan. We deal with the unbounded model, where B is sufficiently large. We first show that no deterministic on-line algorithm can have a competitive ratio of less than $1+(\sqrt{m^{2}+4}-m)/2$ , where m is the number of parallel batch machines. We then present an on-line algorithm which is the one best possible for any specific values of m.
---
paper_title: An on-line algorithm for the single machine unbounded parallel-batching scheduling with large delivery times

paper_content:

We consider the on-line version of the single machine unbounded parallel-batching scheduling with delivery times of jobs. Each [email protected]?s information, such as processing time p"j and delivery time q"j, is not known in advance and becomes known at its arrival time. Once the processing of a job is completed, we deliver it to the destination. Here, the time is continuous. The objective is to minimize the time by which all jobs have been delivered. In this paper, we consider job system with large delivery times, i.e., q"j>=p"j, for each job J"j. We provide an on-line algorithm with a competitive ratio (5+1)/2~1.618 and show that any on-line algorithm has a competitive ratio of at least (3+1)/2~1.366.
---
paper_title: Online batch scheduling on parallel machines with delivery times

paper_content:

We study the online batch scheduling problem on parallel machines with delivery times. Online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m=2 or m=3, respectively. When m≥4, we present an online algorithm with a competitive ratio of 1.5+o(1).
---
paper_title: Online scheduling on unbounded parallel-batch machines with incompatible job families

paper_content:

We consider online scheduling on m parallel-batch machines where the batch capacity is unbounded and the jobs belong to m incompatible job families. By incompatible job families, we mean that jobs from different families cannot be processed together in the same batch. The processing time of a job becomes known only upon its arrival. The objective is to minimize the makespan. The problem is difficult to solve so we consider the case where the number of families is equal to the number of machines. We give a lower bound 5+12~1.618 on the competitive ratio of any online algorithm for this restricted problem. We also provide an online algorithm H"m(@q), where @q@?(0,1) is a parameter, and show that its competitive ratio is no less than 1+105~1.632. When m=2 or under the condition that jobs belonging to the same family have identical processing times, we show that H"m(@a), where @a=5-12, is a best possible online algorithm. When m>=3, we prove that H"m(@b), where @b=2-1, has a competitive ratio no greater than 1+1@b+1~1.707.
---
paper_title: An improved on-line algorithm for single parallel-batch machine scheduling with delivery times

paper_content:

We study an on-line single parallel-batch machine scheduling problem where each job has a processing time and a delivery time. Jobs arrive over time and the batch capacity is unbounded. Jobs can be processed in a common batch, and each job is delivered independently and immediately at its completion time on the machine. The objective is to minimize the time by which all the jobs are delivered. We provide an on-line algorithm with a competitive ratio 22-1~1.828, which improves on a 2-competitive on-line algorithm for this problem in the literature.
---
paper_title: Online scheduling on unbounded parallel-batch machines to minimize the makespan

paper_content:

We consider online scheduling on m parallel-batch machines to minimize the makespan where the batch capacity is unbounded. The processing time of a job becomes known only upon its arrival. We give an improved lower bound [email protected]"m on the competitive ratio, where @a"m is the positive solution of the equation @a"m^[email protected]"m-1=0, and establish a best possible online algorithm matching this lower bound. We also provide a new lower bound 3/2 on the competitive ratio for dense-algorithms, and present a best possible dense-algorithm matching this lower bound.
---
paper_title: An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines

paper_content:

We consider the problem of on-line scheduling a set of n jobs on two parallel batch processing machines. The objective is to minimize the makespan. We provide an algorithm for the problem that is better than one given in the literature, improving the competitive ratio from 32 to 2.
---
paper_title: On-Line Scheduling Algorithms for a Batch Machine with Finite Capacity

paper_content:

We study the problem of on-line scheduling jobs with release dates on a batch machine of finite capacity with the objective of minimizing the makespan. We generalize several existing algorithms for the problem to a class of on-line algorithms that are 2-competitive for any arbitrary finite machine capacity. Then, we show that one of these generalized algorithms is in fact 7/4-competitive for machine capacity 2. This is the first on-line algorithm for a finite machine capacity with competitive ratio less than 2.
---
paper_title: Online unbounded batch scheduling on parallel machines with delivery times

paper_content:

We consider the online unbounded batch scheduling problems on $$m$$ m identical machines subject to release dates and delivery times. Jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Jobs can be processed in a common batch and the batch capacity is unbounded. Once the processing of a job is completed it is independently delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job $$J_j$$ J j , its processing time and delivery time are denoted by $$p_j$$ p j and $$q_j$$ q j , respectively. We first consider a restricted model: the jobs have agreeable processing and delivery times, i.e., for any two jobs $$J_i$$ J i and $$J_j\,p_i>p_j$$ J j p i > p j implies $$q_i\ge q_j$$ q i ? q j . For the restrict case, we provide a best possible online algorithm with competitive ratio $$1+\alpha _m$$ 1 + ? m , where $$\alpha _m>0$$ ? m > 0 is determined by $$\alpha _m^2+m\alpha _m=1$$ ? m 2 + m ? m = 1 . Then we present an online algorithm with a competitive ratio of $$1+2/\lfloor \sqrt{m}\rfloor $$ 1 + 2 / ? m ? for the general case.
---
paper_title: Approximation Algorithms in Batch Processing

paper_content:

AbstractA polynomial approximation scheme for minimizing makespan in a batch processing system under dynamic job arrivals is presented. A lower bound of ::: $${{(\sqrt 5 + 2)} \mathord{\left/ {\vphantom {{(\sqrt 5 + 2)} 2}} \right. \kern-\nulldelimiterspace} 2}$$ ::: on the competitive ratio of any on-line algorithm is proved. This is matched by an on-line algorithm for the special case of unbounded machine capacity.
---
paper_title: On‐line algorithms for minimizing makespan on batch processing machines

paper_content:

We consider problem of scheduling jobs on-line on batch processing machines with dynamic job arrivals to minimize makespan. A batch machine can handle up to B jobs simultaneously. The jobs that are processed together from a batch, and all jobs in a batch start and complete at the same time. 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. In the first part of this paper, we address the single batch processing machine scheduling problem. First we deal with two variants: the unbounded model where B is sufficiently large and the bounded model where jobs have two distinct arrival times. For both variants, we provide on-line algorithms with worst-case ratio (the inverse of the Golden ratio) and prove that these results are the best possible. Furthermore, we generalize our algorithms to the general case and show a worst-case ratio of 2. We then consider the unbounded case for parallel batch processing machine scheduling. Lower bound are given, and two on-line algorithms are presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 241–258, 2001
---
paper_title: Online scheduling on unbounded parallel-batch machines to minimize maximum flow-time

paper_content:

We consider online scheduling on m unbounded parallel-batch machines to minimize maximum flow-time of the jobs. We show that no online algorithm can have a competitive ratio less than [email protected]"m, where @a"m is the positive root of @a^2+(m+1)@a-1=0, and this lower bound is still valid even when all jobs have the same processing times. Then we provide an online algorithm of competitive ratio 1+1/m. When the jobs have the same processing times, we present a best possible online algorithm of competitive ratio [email protected]"m.
---
paper_title: On-Line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time

paper_content:

Scheduling a batch processing system has been extensively studied in the last decade. A batch processing system is modelled as a machine that can process up to b jobs simultaneously as a batch. The scheduling problems involves assigning all n jobs to batches and determining the batch sequence in such a way that certain objective function of job completion times C, is minimized. In this paper, we address the scheduling problem under the on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job that may arrive later. Our objective is to minimize the total weighted completion time Σw j C j . We provide a linear time on-line algorithm for the unrestrictive model (i.e., b ≥ n) and show that the algorithm is 10/3-competitive. For the restrictive model (i.e., b 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees.
---

<format>
Title: Online Over Time Scheduling on Parallel-Batch Machines: A Survey

Section 1: Introduction
Description 1: Introduce the concept of online over time scheduling on parallel-batch machines, its importance, and motivation.

Section 2: Parallel-Batch Scheduling
Description 2: Discuss the fundamental model and applications of parallel-batch scheduling, including its origin and significance in semiconductor manufacturing.

Section 3: Online Scheduling
Description 3: Define online scheduling and explain the challenges and characteristics of scheduling jobs that arrive over time with no advance information.

Section 4: Competitive Ratio
Description 4: Explain the concept of competitive ratio as a measure of the quality of online algorithms and discuss the lower and upper bounds of competitive ratios.

Section 5: Online Scheduling Algorithms to Minimize Makespan
Description 5: Survey the various online algorithms developed to minimize makespan on parallel-batch machines, including delay and greedy algorithms.

Section 6: Online Scheduling with Delivery Times
Description 6: Review the studies focusing on online scheduling problems with delivery times and the objective to minimize the maximum delivery time (D_max).

Section 7: Semi-Online Scheduling
Description 7: Describe the semi-online scheduling scenario where some job information is known in advance, and summarize the key research findings.

Section 8: Open Problems
Description 8: Present the open problems in the field of online over time scheduling on parallel-batch machines for further research.

Section 9: Other Results
Description 9: Discuss additional results related to different objectives, such as minimizing maximum flow time and total weighted completion times, in the context of online scheduling.

</format>
