Two-Dimensional Scheduling: A Review
---
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: Scheduling with batching: A review

paper_content:

There is an extensive literature on models that integrate scheduling with batching decisions. Jobs may be batched if they share the same setup on a machine. Another reason for batching occurs when a machine can process several jobs simultaneously. This paper reviews the literature on scheduling with batching, giving details of the basic algorithms, and referencing other significant results. Special attention is given to the design of efficient dynamic programming algorithms for solving these types of problems.
---
paper_title: Efficient scheduling algorithms for a single batch processing machine

paper_content:

Scheduling problems of a batch processing machine are solved by efficient algorithms. On a batch processing machine, multiple jobs can be processed simultaneously in a batch form. We call the number of jobs in the batch the batch size, which can be any integer between 1 and k, a predetermined integer of the maximum batch size. The process time of a batch is constant and independent of the batch size. Preemption is not allowed. Given n jobs with release times r"1 and due dates d"i, i = 1...., n, we give efficient algorithms to find a feasible schedule, if any, which minimizes the final completion time under the assumption such that for r"i > r"j, d"i >= d"j. Some industrial applications are discussed.
---
paper_title: An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes

paper_content:

This paper addresses the problem of scheduling jobs with non-identical sizes on a single batch processing machine. A batch processing machine is one which can process multiple jobs simultaneously as a batch as long as the total size of jobs being processed does not exceed the machine capacity. The batch processing time is equal to the longest processing time among all jobs in the batch. For the simultaneous minimization of the bi-criteria of makespan and maximum tardiness, we propose two different multi-objective genetic algorithms based on different representation schemes. While the first algorithm do search via generating sequences of jobs using genetic operators and then batching jobs keeping their order in the sequence, the second algorithm uses the idea of generating batches of jobs directly using genetic operators and ensures feasibility through using heuristic procedures. The type of representation used in the second algorithm allows introducing heuristics with the ability of biasing the search towards each objective and also allows hybridization with a local search heuristic that gives the ability of finding Pareto-optimal or locally efficient Pareto-solutions. Computational results show that the non-dominated solutions obtained by the latter algorithm are very superior in closeness to the true Pareto-optimal solutions and to keep diversity in the obtained Pareto-set, as the problem size increases.
---
paper_title: Heuristics for minimizing total completion time and maximum lateness on identical parallel machines with setup times

paper_content:

This paper aims at minimizing the total completion time together with the maximum lateness. Jobs are processed by parallel machines in batches. A setup is required before processing a batch, which is common for all jobs in the batch. Jobs are continuously processed after the setup time. The processing length of a batch is the sum of the setup time and processing times of the jobs it contains. Due to the availability constraint, the completion time of a job is the time when a batch is totally processed. Considering due dates, the jobs need to be processed in a way that the total completion time and the maximum lateness are minimized. This problem is a kind of NP-hard so first we present a constructive heuristic to solve the problem. Then we propose a genetic algorithm whose initial population is formed by using the heuristic approach. Computational experiments are carried out to evaluate the performance of the proposed algorithms.
---
paper_title: A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes

paper_content:

In this paper, we consider the scheduling problem on a single batch processing machine with non-identical job sizes; in which the machine has a limited capacity and can process a group of jobs simultaneously as a batch. The processing time of a batch is the longest processing time of all jobs in the batch. The objective is to minimize the makespan. We formulate the problem using Dantzig-Wolfe decomposition as a set partitioning problem. Based on the set partitioning formulation, we present a tight lower bound using column generation method. A heuristic algorithm is also developed to generate the basic solution in the column generation method. A branch and price algorithm which combines the column generation technique with branch and bound method is then presented to obtain the optimal solution of the problem. The efficiency of the proposed branch and price algorithm is ultimately compared to the branch and bound algorithm from the literature, based on the generated sample problems.
---
paper_title: A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes

paper_content:

This paper investigates the scheduling problem of parallel identical batch processing machines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and processing time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Based on developing heuristic approaches, we proposed a hybrid genetic heuristic (HGH) to minimize makespan objective. To verify the performance of our algorithm, comparisons are made through using a simulated annealing (SA) approach addressed in the literature as a comparator algorithm. Computational experiments reveal that affording the knowledge of problem through using heuristic procedures, gives HGH the ability of finding optimal or near optimal solutions in a reasonable time.
---
paper_title: Minimizing total weighted tardiness on a single batch process machine with incompatible job families

paper_content:

The diffusion step in semiconductor wafer fabrication is very time consuming, compared to other steps in the process, and performance in this area has a significant impact on overall factory performance. Diffusion furnaces are able to process multiple lots of similar wafers at a time, and are therefore appropriately modeled as batch processing machines with incompatible job families. Due to the importance of on-time delivery in semiconductor manufacturing, we focus on minimizing the total weighted tardiness in this environment. The resulting problem is NP-Hard, and we decompose it into two sequential decision problems: assigning lots to batches followed by sequencing the batches. We develop several heuristics for these subproblems and test their performance.
---
paper_title: Managing Batch Processors to Reduce Lead Time in a Semiconductor Packaging Line

paper_content:

In this paper we study a semiconductor packaging line at IBM Bromont. At the line, modules are assembled and then tested in a Burn-in oven. The Burn-in oven is a batch processing station. We outline a procedure to determine order release scheduled and lot sizes for the various work stations in the line, such that total manufacturing lead time is minimized. The internal parameters of the procedure are set by simulation experiments and by heuristics. Sensitivity analysis is carried out to determine the robustness of the procedure with respect to various external parameter settings.
---
paper_title: The Batch Loading and Scheduling Problem

paper_content:

This paper discusses the problem of batching and scheduling of certain kinds of batch processors. Examples of these processors include heat treatment facilities, particularly in the steel and ceramics industries, as well as a variety of operations in the manufacture of integrated circuits. In general, for our problem there is a set of jobs waiting to be processed. Each job is associated with a given family and has a weight or delay cost and a volume. The scheduler must organize jobs into batches in which each batch consists of jobs from a single family and in which the total volume of jobs in a batch does not exceed the capacity of the processor. The scheduler must then sequence all the batches. The processing time for a batch depends only on the family and not on the number or the volume of jobs in the batch. The objective is to minimize the mean weighted flow time.The paper presents an integer programming formulation for this problem, generates a lower bound from a partial LP relaxation, provides a polynomial algorithm to solve a special case, and tests a set of heuristics on the general problem. The ability to pack jobs into batches is the key to efficient solutions and is the basis of the different solution procedures in this paper. The heuristics include a greedy heuristic, a successive knapsack heuristic, and a generalized assignment heuristic. Optimal solutions are obtained by complete enumeration for small problems.The conclusions of the computational study show that the successive knapsack and generalized assignment heuristics perform better than the greedy. The generalized assignment heuristic does slightly better than the successive knapsack heuristic in some cases, but the latter is substantially faster and more robust. For problems with few jobs, the generalized assignment heuristic and the knapsack heuristic almost always provide optimal solutions. For problems with more jobs, we compare the heruistic solutions' values to lower bounds; the computational work suggests that the heuristics continue to provide solutions that are optimal or close to the optimal. The study also shows that the volume of the job relative to the capacity of the facility and the number of jobs in a family affect the performance of the heuristics, whereas the number of families does not. Finally, we give a worst-case analysis of the greedy heuristic.
---
paper_title: Minimizing total completion time on a batch processing machine with job families

paper_content:

We consider the problem of minimizing the total completion time on a single batch processing machine. The set of jobs to be scheduled can be partitioned into a number of families, where all jobs in the same family have the same processing time. The machine can process at most B jobs simultaneously as a batch, and the processing time of a batch is equal to the processing time of the longest job in the batch. We analyze that properties of an optimal schedule and develop a dynamic programming algorithm of polynomial time complexity when the number of job families is fixed. The research is motivated by the problem of scheduling burn-in ovens in the semiconductor industry.
---
paper_title: Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime

paper_content:

This paper addresses a problem of batch scheduling which arises in the burn-in stage of semiconductor manufacturing. Burn-in ovens are modeled as batch-processing machines which can handle up to B jobs simultaneously. The processing time of a batch is equal to the longest processing time among the jobs in the batch. The scheduling problem involves assigning jobs to batches and determining the batch sequence so as to minimize the total flowtime. In practice, there is a small number m of distinct job types. Previously, the only solution techniques known for the single-machine version of this problem were an O(m23Bm+1) pseudopolynomial algorithm, and a branch-and-bound procedure. We present an algorithm with a running time of O(m23m), which is independent of B, the maximum batch size. We also present a polynomial heuristic for the general problem (when m is not fixed), which is a two-approximation algorithm. For any problem instance, this heuristic provides a solution at least as good as that given by previo...
---
paper_title: A genetic algorithm to minimize maximum lateness on a batch processing machine

paper_content:

We consider the problem of minimizing maximum lateness on a batch processing machine in the presence of dynamic job arrivals. The batch processing machine can process up to B jobs simultaneously, and the processing time of a batch is given by that of the job with the longest processing time in the batch. We adapt a dynamic programming algorithm from the literature to determine whether a due-date feasible batching exists for a given job sequence. We then combine this algorithm with a random keys encoding scheme to develop a genetic algorithm for this problem. Computational experiments indicate that this algorithm has excellent average performance with reasonable computational burden.
---
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: Scheduling a single batch processing machine with non-identical job sizes

paper_content:

The problem of scheduling jobs with non-identical capacity requirements or sizes on a single batch processing machine to minimize total completion time and makespan is studied. These problems are proven to be NP-hard and heuristics are developed for both, as well as a branch and bound algorithm for the total completion time problem. Computational experiments show that the heuristics are capable of rapidly obtaining near-optimal solutions.
---
paper_title: A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families

paper_content:

We consider the problem of minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals. We propose a family of iterative improvement heuristics based on previous work by Potts [Analysis of a heuristic for one machine sequencing with release dates and delivery times. Operations Research 1980;28:1436-41] and Uzsoy [Scheduling batch processing machines with incompatible job families. International Journal for Production Research 1995;33(10):2685-708] and combine them with a genetic algorithm (GA) based on the random keys encoding of Bean [Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing 1994;6(2):154-60]. Extensive computational experiments show that one of the proposed GAs runs significantly faster than the other, providing a good tradeoff between solution time and quality. The combination of iterative heuristics with GAs consistently outperforms the iterative heuristics on their own.
---
paper_title: Scheduling a single batch processing machine with secondary resource constraints

paper_content:

This paper studies the problems of minimizing total completion time (ΣCi) and makespan (Cmax) on a single batch processing machine with job families and secondary resource constraints. The motivation for this problem is the burn-in operation in the final testing stage of semiconductor manufacturing, where both oven capacity and the number of boards available may constrain scheduling decisions. Because both problems are NP-hard, integer programming formulations are developed for special cases and are then used to develop heuristics. Extensive computational experiments show that the heuristics are capable of consistently obtaining good solutions in modest CPU times.
---
paper_title: Minimizing total completion time on batch processing machines

paper_content:

We study the problem of minimizing total completion time on single and parallel batch processing machines. A batch processing machine is one which 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. This problem is motivated by burn-in operations in the final testing stage of semiconductor manufacturing and is expected to occur in other production environments. We provide an exact solution procedure for the single-machine problem and heuristic algorithms for both single and parallel machine problems. While the exact algorithms have limited applicability due to high computational requirements, extensive experiments show that the heuristics are capable of consistently obtaining near-optimal solutions in very reasonable CPU times.
---
paper_title: Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes

paper_content:

This paper considers the parallel batch processing machine scheduling problem which involves the constraints of unequal ready times, non-identical job sizes, and batch dependent processing times in order to sequence batches on identical parallel batch processing machines with capacity restrictions. This scheduling problem is a practical generalisation of the classical parallel batch processing machine scheduling problem, which has many real-world applications, particularly, in the aging test operation of the module assembly stage in the manufacture of thin film transistor liquid crystal displays (TFT-LCD). The objective of this paper is to seek a schedule with a minimum total completion time for the parallel batch processing machine scheduling problem. A mixed integer linear programming (MILP) model is proposed to optimise the scheduling problem. In addition, to solve the MILP model more efficiently, an effective compound algorithm is proposed to determine the number of batches and to apply this number as...
---
paper_title: Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times

paper_content:

This research is motivated by a scheduling problem found in the diffusion and oxidation areas of semiconductor wafer fabrication, where the machines can be modeled as parallel batch processors. We attempt to minimize total weighted tardiness on parallel batch machines with incompatible job families and unequal ready times of the jobs. Given that the problem is NP-hard, we propose two different decomposition approaches. The first approach forms fixed batches, then assigns these batches to the machines using a genetic algorithm (GA), and finally sequences the batches on individual machines. The second approach first assigns jobs to machines using a GA, then forms batches on each machine for the jobs assigned to it, and finally sequences these batches. Dispatching and scheduling rules are used for the batching phase and the sequencing phase of the two approaches. In addition, as part of the second decomposition approach, we develop variations of a time window heuristic based on a decision theory approach for forming and sequencing the batches on a single machine.
---
paper_title: Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness

paper_content:

This research is motivated by a scheduling problem found in the diffusion and oxidation areas of semiconductor wafer fabrication, where the machines can be modelled as parallel batch processors. We attempt to minimize total weighted tardiness on parallel batch machines with incompatible job families. Given that the problem is NP-hard, we propose two different versions of a genetic algorithm (GA), each consisting of three different phases. The first version forms fixed batches, then assigns batches to the machines using a GA, and finally sequences the batches on individual machines. The second version assigns jobs to machines using a GA, then forms batches on each machine for the jobs assigned to it, and finally sequences these batches. Heuristics are used for the batching phase and the sequencing phase. For both these versions an additional fourth phase can be included wherein the sequenced batches are modified using pairwise swapping techniques. Using stochastically generated test data we show that algorithms of the first version of the GA outperform (1) traditional dispatching rules with respect to solution quality and (2) the algorithms of the second version with respect to both solution quality and computation time.
---
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: Heuristics for makespan minimization on parallel batch processing machines with unequal job ready times.

paper_content:

This research aims at minimizing the makespan of a set of identical batch processing machines arranged in parallel. Each job is defined by its processing time, ready time, and size. Each machine can process several jobs simultaneously as long as the machine capacity is not exceeded. The batch processing and ready times depend upon the batch composition. The batch processing time is equal to the longest processing job in the batch, and the batch ready time is equal to the largest ready time among those jobs in the batch. The problem under study is NP-hard. Consequently, a constructive heuristic is proposed and its performance with respect to solution quality and computational cost is compared against other solution approaches found in the literature. The computational experiments on a set of randomly generated instances show that the performance of the proposed heuristic is competitive with respect to solution quality and requires little computational cost.
---
paper_title: Scheduling batch processing machines with incompatible job families

paper_content:

The problem of scheduling a single batch processing machine with incompatible job families was studied, where jobs of different families cannot be processed together in the same batch. First static problems where all jobs are available simultaneously were considered and showed that for a regular performance measure there will be no unnecessary partial batches. This allowed us to develop efficient optimal algorithms to minimize makespan (Cmax), maximum lateness (Lmax) and total weighted completion time and apply some of these results to problems with parallel identical batch processing machines. Then problems withdynamic job arrivals were considered and an efficient optimal algorithm for minimizing Cmax and several heuristics to minimize Lmax were provided. Computational experiments showed that the heuristics developed for the latter problem consistently improve on dispatching solutions in very reasonable CPU times.
---
paper_title: Solving the parallel batch-processing machines with different release times, job sizes, and capacity limits by metaheuristics

paper_content:

This study addresses the scheduling problem of parallel batch-processing machines encountered in different manufacturing environments, such as the burn-in operation in the manufacture of semiconductors and the aging test operation in the manufacture of thin film transistor-liquid crystal displays (TFT-LCDs). Each machine simultaneously processes several jobs in a batch, as long as the total size of all jobs in the batch does not exceed machine capacity. The processing time of a batch is represented by the longest time among the jobs in the batch. For this problem, a mixed integer programming (MIP) model is provided, and metaheuristics based on simulated annealing (SA) and genetic algorithm (GA) are proposed. In the proposed GA and SA, a string with (n+m-1) numbers is used to assign jobs into each machine. The multi-stage dynamic programming (MSDP) algorithm, taken from the dynamic programming (DP) algorithm of Chou in 2007, is then applied to group the jobs into batches for each machine. The experimental results show that the proposed metaheuristic techniques were successfully employed in solving the scheduling problems of parallel batch-processing machines with makespan criterion.
---
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: Scheduling a single batch processing machine with non-identical job sizes

paper_content:

The problem of scheduling jobs with non-identical capacity requirements or sizes on a single batch processing machine to minimize total completion time and makespan is studied. These problems are proven to be NP-hard and heuristics are developed for both, as well as a branch and bound algorithm for the total completion time problem. Computational experiments show that the heuristics are capable of rapidly obtaining near-optimal solutions.
---
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: Minimizing makespan on a single batching machine with release times and non-identical job sizes

paper_content:

We consider the problem of scheduling jobs with release times and non-identical job sizes on a single batching machine; our objective is to minimize makespan. We present an approximation algorithm with worst-case ratio 2+@e, where @e>0 can be made arbitrarily small.
---
paper_title: Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure

paper_content:

Abstract A batch processing machine can simultaneously process several jobs forming a batch. This paper considers the problem of scheduling jobs with non-identical capacity requirements, on a single-batch processing machine of a given capacity, to minimize the makespan. The processing time of a batch is equal to the largest processing time of any job in the batch. We present some dominance properties for a general enumeration scheme and for the makespan criterion, and provide a branch and bound method. For large-scale problems, we use this enumeration scheme as a heuristic method. Scope and purpose Usually in classical scheduling problems, a machine can perform only one job at a time. Although, one can find machines that can process several jobs simultaneously as a batch. All jobs of a same batch have common starting and ending times. Batch processing machines are encountered in many different environments, such as burn-in operations in semiconductor industries or heat treatment operations in metalworking industries. In the first case, the capacity of the machine is defined by the number of jobs it can hold. In the second case, each job has a certain capacity requirement and the total size of a batch cannot exceed the capacity of the machine. Hence, the number of jobs contained in each batch may be different. In this paper, we consider this second case (which is more difficult) and we provide an exact method for the makespan criterion (minimizing the last ending time).
---
paper_title: Scheduling a single batch processing machine with non-identical job sizes

paper_content:

The problem of scheduling jobs with non-identical capacity requirements or sizes on a single batch processing machine to minimize total completion time and makespan is studied. These problems are proven to be NP-hard and heuristics are developed for both, as well as a branch and bound algorithm for the total completion time problem. Computational experiments show that the heuristics are capable of rapidly obtaining near-optimal solutions.
---
paper_title: Minimizing makespan on a single batch processing machine with non-identical job sizes : A hybrid genetic approach

paper_content:

This paper addresses minimizing makespan by genetic algorithm (GA) for scheduling jobs with non-identical sizes on a single batch processing machine. We propose two different genetic algorithms based on different encoding schemes. The first one is a sequence based GA (SGA) that generates random sequences of jobs and applies the batch first fit (BFF) heuristic to group the jobs. The second one is a batch based hybrid GA (BHGA) that generates random batches of jobs and ensures feasibility through using knowledge of the problem. A pairwise swapping heuristic (PSH) based on the problem characteristics is hybridized with BHGA that has the ability of steering efficiently the search toward the optimal or near optimal schedules. Computational results show that BHGA performs considerably well compared with a modified lower bound and significantly outperforms the SGA and a simulated annealing (SA) approach addressed in literature. In comparison with a constructive heuristic named FFLPT, BHGA also shows its superiority.
---
paper_title: Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing

paper_content:

Abstract This research proposes a simulated annealing (SA) approach to minimize makespan for a single batch-processing machine. Each job has a corresponding processing time and size. The machine can process the jobs in batches as long as the machine capacity is not exceeded. The processing time of a batch is equal to the longest processing time among all jobs in the batch. Random instances were generated to test our approach with respect to solution quality and run time. The results of the SA approach were compared to CPLEX. Our approach outperforms CPLEX on all the instances.
---
paper_title: A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes

paper_content:

This paper investigates the scheduling problem of parallel identical batch processing machines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and processing time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Based on developing heuristic approaches, we proposed a hybrid genetic heuristic (HGH) to minimize makespan objective. To verify the performance of our algorithm, comparisons are made through using a simulated annealing (SA) approach addressed in the literature as a comparator algorithm. Computational experiments reveal that affording the knowledge of problem through using heuristic procedures, gives HGH the ability of finding optimal or near optimal solutions in a reasonable time.
---
paper_title: A genetic algorithm to minimize maximum lateness on a batch processing machine

paper_content:

We consider the problem of minimizing maximum lateness on a batch processing machine in the presence of dynamic job arrivals. The batch processing machine can process up to B jobs simultaneously, and the processing time of a batch is given by that of the job with the longest processing time in the batch. We adapt a dynamic programming algorithm from the literature to determine whether a due-date feasible batching exists for a given job sequence. We then combine this algorithm with a random keys encoding scheme to develop a genetic algorithm for this problem. Computational experiments indicate that this algorithm has excellent average performance with reasonable computational burden.
---
paper_title: Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms

paper_content:

Abstract This paper aims at minimizing the makespan for a batch-processing machine. The processing times and the sizes of the jobs are known. The machine can process a batch as long as its capacity is not exceeded. The processing time of a batch is the longest processing time of all the jobs in that batch. This problem is NP-hard and hence a genetic algorithm (GA) approach is proposed. Random instances were used to test the effectiveness of the proposed approach. The results obtained from GA were compared with a simulated annealing approach and a commercial solver. The results indicate that the GA was able to arrive at better makespan with shorter run times.
---
paper_title: A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families

paper_content:

We consider the problem of minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals. We propose a family of iterative improvement heuristics based on previous work by Potts [Analysis of a heuristic for one machine sequencing with release dates and delivery times. Operations Research 1980;28:1436-41] and Uzsoy [Scheduling batch processing machines with incompatible job families. International Journal for Production Research 1995;33(10):2685-708] and combine them with a genetic algorithm (GA) based on the random keys encoding of Bean [Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing 1994;6(2):154-60]. Extensive computational experiments show that one of the proposed GAs runs significantly faster than the other, providing a good tradeoff between solution time and quality. The combination of iterative heuristics with GAs consistently outperforms the iterative heuristics on their own.
---
paper_title: Genetic Algorithms and Random Keys for Sequencing and Optimization

paper_content:

In this paper we present a general genetic algorithm to address a wide variety of sequencing and optimization problems including multiple machine scheduling, resource allocation, and the quadratic assignment problem. When addressing such problems, genetic algorithms typically have difficulty maintaining feasibility from parent to offspring. This is overcome with a robust representation technique called random keys . Computational results are shown for multiple machine scheduling, resource allocation, and quadratic assignment problems. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
---
paper_title: Minimizing makespan on a single batch processing machine with non-identical job sizes : A hybrid genetic approach

paper_content:

This paper addresses minimizing makespan by genetic algorithm (GA) for scheduling jobs with non-identical sizes on a single batch processing machine. We propose two different genetic algorithms based on different encoding schemes. The first one is a sequence based GA (SGA) that generates random sequences of jobs and applies the batch first fit (BFF) heuristic to group the jobs. The second one is a batch based hybrid GA (BHGA) that generates random batches of jobs and ensures feasibility through using knowledge of the problem. A pairwise swapping heuristic (PSH) based on the problem characteristics is hybridized with BHGA that has the ability of steering efficiently the search toward the optimal or near optimal schedules. Computational results show that BHGA performs considerably well compared with a modified lower bound and significantly outperforms the SGA and a simulated annealing (SA) approach addressed in literature. In comparison with a constructive heuristic named FFLPT, BHGA also shows its superiority.
---
paper_title: Using genetic algorithms for single-machine bicriteria scheduling problems

paper_content:

Abstract We consider two bicriteria scheduling problems on a single machine: minimizing flowtime and number of tardy jobs, and minimizing flowtime and maximum earliness. Both problems are known to be NP-hard. For the first problem, we developed a heuristic that produces an approximately efficient solution (AES) for each possible value the number of tardy jobs can take over the set of efficient solutions. We developed a genetic algorithm (GA) that further improves the AESs. We then adapted the GA for the second problem by exploiting its special structure. We present computational experiments that show that the GAs perform well. Many aspects of the developed GAs are quite general and can be adapted to other multiple criteria scheduling problems.
---

Title: Two-Dimensional Scheduling: A Review

Section 1: INTRODUCTION
Description 1: This section provides an overview and background of Two-Dimensional Scheduling, its significance in manufacturing industries, and the objectives of the study.

Section 2: PROBLEM SPECIFICATIONS
Description 2: This section describes the assumptions, mathematical models, and constraints of the Two-Dimensional Scheduling problem.

Section 3: LITERATURE REVIEW
Description 3: This section reviews existing research and literature on batch scheduling problems, focusing on single and parallel batch processing machines with different job sizes and family compatibilities.

Section 4: METHODOLOGY AND ANALYSIS
Description 4: This section covers the proposed classification of batch processing problems, complexity analysis, competitive ratio analysis, branch and bound approaches, heuristic algorithms, and meta-heuristic (intelligent) algorithms applied to Two-Dimensional Scheduling. 

Section 5: CONCLUSION
Description 5: This section summarizes the study's findings, acknowledging the NP-hard nature of the problem, and highlights the limited number of studies on branch and bound and approximation algorithms.

Section 6: ACKNOWLEDGMENT
Description 6: This section acknowledges the financial support and resources provided for conducting the study.