Genetic algorithms for minimizing makespan in a flow shop with two capacitated batch processing machines

This paper considers a flow shop with two batch processing machines. The processing times of the job and their sizes are given. The batch processing machines can process multiple jobs simultaneously in a batch as long as the total size of all the jobs in a batch does not exceed its capacity. When the jobs are grouped into batches, the processing time of the batch is defined by the longest processing job in the batch. Batch processing machines are expensive and a bottleneck. Consequently, the objective is to minimize the makespan (or maximize the machine utilization). The scheduling problem under study is NP-hard, hence, a genetic algorithm (GA) is proposed. The effectiveness (in terms of solution quality and run time) of the GA approach is compared with a simulated annealing approach, a heuristic, and a commercial solver which was used to solve a mixed-integer formulation of the problem. Experimental study indicates that the GA approach outperforms the other approaches by reporting better solution.     

Minimizing makespan in a two-machine no-wait flow shop with batch processing machines

Given a set of jobs and two batch processing machines (BPMs) arranged in a flow shop environment, the objective is to batch the jobs and sequence the batches such that the makespan is minimized. The job sizes, ready times, and processing times on the two BPMs are known. The batch processing machines can process a batch of jobs as long as the total size of all the jobs assigned to a batch does not exceed its capacity. Once the jobs are batched, the processing time of the batch on the first machine is equal to the longest processing job in the batch; processing time of the batch on the second machine is equal to the sum of processing times of all the jobs in the batch. The batches cannot wait between two machines (i.e., no-wait). The problem under study is NP-hard. We propose a mathematical formulation and present a particle swarm optimization (PSO) algorithm. The solution quality and run time of PSO is compared with a commercial solver used to solve the mathematical formulation. Experimental study clearly highlights the advantages, in terms of solution quality and run time, of using PSO to solve large-scale problems.     

Lot streaming in a two-machine mixed shop

Most classical scheduling models overlook the fact that products are often produced in job lots and assume that job lots are indivisible single entities, although an entire job lot consists of many identical items. However, splitting an entire lot (process batch) into sublots (transfer batches) to be moved to downstream machines allows the overlapping of different operations on the same product while work needs to be completed on the upstream machine. This approach is known as lot streaming in scheduling theory. In this study, the lot streaming problem of multiple jobs in a two-machine mixed shop where there are two different job types as flow shop and open shop is addressed so as to minimize the makespan. The optimal solution method is developed for the mixed shop scheduling problem in which lot streaming can improve the makespan.     

A conflict-based priority dispatching rule and operation-based approaches to job shops

Job shop scheduling (JSS) problems consist of a set of machines and a collection of jobs to be scheduled. Each job consists of several operations with a specified processing order. In this paper, a job shop model problem is scheduled with the help of the Giffler and Thompson algorithm using a priority dispatching rule (PDR). A conflict based PDR is used to schedule the job shop model by using Genetic Algorithms (GAs). An iterative method is applied to the job model to find the optimal conflict-based PDR order and the operation sequence. The same job shop model is also scheduled based on an operation using simulated annealing (SA) and hybrid simulated annealing (HSA). A makespan of the job model is used as an objective. These four methods are considered as different solutions for each problem. A two-way analysis of variance (ANOVA) is applied to test its significance.     

Particle swarm optimization for scheduling batch processing machines in a permutation flowshop

Batch processing machines are capable of processing several jobs in a batch simultaneously. These machines are used in many real-life applications. This paper presents solution approaches to schedule batch processing machines arranged in a permutation flowshop in order to minimize its makespan (or completion time of the last batch). The processing time of each job on all the machines and their sizes are given. Each machine can process a batch of jobs as long as its capacity is not violated. The batch processing time is equal to the longest processing job in the batch. Since the problem under study is NP-hard, commercial mixed-integer solvers may require prohibitively long run time to solve even modest sized problems. Consequently, a particle swarm optimization (PSO) algorithm is proposed. Three heuristics to update the particle’s positions are also proposed. The effectiveness of the proposed PSO algorithm is compared with a commercial solver (which was used to solve a mathematical model) and several heuristics from the literature. The experimental study conducted indicates that the proposed PSO algorithm outperforms both the commercial solver and the heuristics in terms of solution quality. The commercial solver requires longer run times compared to PSO.     

GRASP to minimize makespan for a capacitated batch-processing machine

This paper presents a Greedy Randomized Adaptive Search Procedure (GRASP) to minimize the makespan of a capacitated batch-processing machine. Given a set of jobs and their processing times and sizes, the objective is to group these jobs into batches and schedule the batches on a single batch-processing machine such that the time taken to complete the last batch of jobs (or makespan) is minimized. The batch-processing machine can process a batch of jobs simultaneously as long as the total size of all the jobs in that batch does not exceed the machine capacity. The batch-processing time is equal to the longest processing time for a job in the batch. It has been shown that the problem under study is non-deterministic polynomial-time hard. Consequently, a GRASP approach was developed. The solution quality of GRASP was compared to other solution approaches such as simulated annealing, genetic algorithm, and a commercial solver through an experimental study. The study helps to conclude that GRASP outperforms other solution approaches, especially on larger problem instances.     

Flow shop scheduling with two batch processing machines and nonidentical job sizes

A batch processing machine can process several jobs simultaneously. In this research, we consider the problem of a two-stage flow shop with two batch processing machines to minimize the makespan. We assume that the processing time of a batch is the longest processing time among all the jobs in that batch and the sizes of the jobs are nonidentical. There is a limitation on batch sizes and the sum of job sizes in a batch must be less than or equal to the machine capacity. Since this problem is strongly nondeterministic polynomial time hard, we propose two heuristic algorithms. The first one is knowledge-based and the other is based on the batch first fit heuristic proposed previously. To further enhance the solution quality, two different simulated annealing (SA) algorithms based on the two constructive heuristics is also developed. Since heuristic methods for this problem has not been proposed previously, a lower bound is developed for evaluating the performance of the proposed methods. Several test problems have been solved by SAs and lower bound method and the results are compared. Computational studies show that both algorithms provide good results but the first SA (ARSA) algorithm considerably outperforms the second one (FLSA). In addition, the results of ARSA algorithm, optimal solutions, and lower bounds are compared for several small problems. The comparisons show that except for one instance, the ARSA could find the optimal solutions and the proposed lower bound provides small gaps comparing with the optimal solutions.     

Minimizing makespan in a group shop with fuzzy release dates and processing times

This paper deals with a fuzzy group shop scheduling problem. The group shop scheduling problem is a general formulation that includes the flow shop, the job shop, and the open shop scheduling problems. Job release dates and processing times are considered to be triangular fuzzy numbers. The objective is to find a job schedule that minimizes the maximum completion time or makespan. First, the problem is formulated in a form of fuzzy programming and then prepared in a form of deterministic mixed binary integer linear programming by applying the chance-constrained programming. To solve the problem, an efficient genetic algorithm hybridized with an improvement procedure is developed. Both Lamarckian and Baldwinian versions are then implemented and evaluated through computational experiments.     

Robust metaheuristics for group scheduling with sequence-dependent setup times in hybrid flexible flow shops

This paper considers group scheduling problem in hybrid flexible flow shop with sequence-dependent setup times to minimize makespan. Group scheduling problem consists of two levels, namely scheduling of groups and jobs within each group. In order to solve problems with this context, two new metaheuristics based on simulated annealing (SA) and genetic algorithm (GA) are developed. A design procedure is developed to specify and adjust significant parameters for SA- and GA-based metaheuristics. The proposed procedure is based on the response surface methodology and two types of objective function are considered to develop multiple-objective decision making model. For comparing metaheuristics, makespan and elapsed time to obtain it are considered as two response variables representing effectiveness and efficiency of algorithms. Based on obtained results in the aspect of makespan, GA-based metaheuristic is recommended for solving group scheduling problems in hybrid flexible flow shop in all sizes and for elapsed time SA-based metaheuristic has better results.     

Analysis of dispatching rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times

Stochastic dynamic job shop scheduling problem with consideration of sequence-dependent setup times are among the most difficult classes of scheduling problems. This paper assesses the performance of nine dispatching rules in such shop from makespan, mean flow time, maximum flow time, mean tardiness, maximum tardiness, number of tardy jobs, total setups and mean setup time performance measures viewpoint. A discrete event simulation model of a stochastic dynamic job shop manufacturing system is developed for investigation purpose. Nine dispatching rules identified from literature are incorporated in the simulation model. The simulation experiments are conducted under due date tightness factor of 3, shop utilization percentage of 90 % and setup times less than processing times. Results indicate that shortest setup time (SIMSET) rule provides the best performance for mean flow time and number of tardy jobs measures. The job with similar setup and modified earliest due date (JMEDD) rule provides the best performance for makespan, maximum flow time, mean tardiness, maximum tardiness, total setups and mean setup time measures.     

Group shop scheduling with uncertain data and a general cost objective

In this paper, a stochastic group shop scheduling problem with a due date-related objective is studied. The group shop scheduling problem provides a general formulation including two other shop scheduling problems, the job shop and the open shop. Both job release dates and processing times are assumed to be random variables with known distributions. Moreover, earliness and tardiness of jobs are penalized at different rates. The objective is to minimize the expected maximum completion cost among all jobs. A lower bound on the objective function is proposed, and then, a hybrid approach following a simulation optimization procedure is developed to deal with the problem. An ant colony optimization algorithm is employed to construct good feasible solutions, while a discrete-event simulation model is used to estimate the performance of each constructed solution that, taking into account its lower bound, may improve the best solution found so far. The proposed approach is then evaluated through computational experiments.     

A modified shifting bottleneck heuristic for the reentrant job shop scheduling problem with makespan minimization

This paper proposes a modified shifting bottleneck heuristic (MSBH) for the reentrant job shop scheduling problem (RJSSP) with makespan minimization objective. Recently, the reentrant job shop has come into prominence as a new type of manufacturing shop. The principle characteristic of a reentrant job shop is that a job may visit certain machines more than once during the process flow, whereas in the classic job shop, each job visits a machine only once. The shifting bottleneck heuristic (SBH) is one of the most successful heuristic approaches for the classical job shop scheduling problem, which decomposes the problem into a number of single-machine subproblems. This paper adapts the SBH for the RJSSP and proposes a new sequencing heuristic for the single-machine maximum lateness subproblem considering the reentrant jobs in order to handle large-size RJSSPs. It also uses a subproblem criticality measure that further shortens the implementation time. The proposed MSBH is tested by using instances up to 20 machines and 100 jobs, and it is illustrated that good quality solutions can be obtained in reasonable computational times. A real-life application of the MSBH is also given as a case study to evaluate its performance.     

A mixed integer programming formulation for scheduling of virtual manufacturing cells (VMCs)

We present a multi-objective mixed integer programming formulation for job scheduling in virtual manufacturing cells (VMCs). In a VMC, machines are dedicated to a part family as in a regular cell, but machines are not physically relocated in a contiguous area. Cell configurations are therefore temporary, and assignments are made to optimize the scheduling objective under changing demand conditions. We consider the case where there are multiple jobs with different processing routes. There are multiple machine types with several identical machines in each type and are located in different locations in the shop floor. The two scheduling objectives are makespan minimization and minimizing total traveling distance. Since batch splitting is permitted in the system, scheduling decisions must tell us the (a) assignment of jobs to the machines, (b) the job starting time at each machine, and (c) the part quantity processed on different machines due to batch splitting. Under these decision variables, the objective function is to minimize the sum of the makespan and total traveling distance/cost. Illustrative examples are given to demonstrate the implementation of the model.     

An improved mixed integer linear formulation and lower bounds for minimizing makespan on a flow shop with batch processing machines

This paper considers a flow shop scheduling problem with batch processing machines. Each batch processing machine has a limited capacity and can process a group of jobs, each of them having a different known capacity requirement, simultaneously. Job processing time on each machine is known and arbitrary. The processing time of a batch on each machine is the longest processing time of all jobs in the batch. We improve the only existing mixed integer linear formulation (MILF) of the problem through significant reduction in size complexity of the model. Results justify that the improved MILF is clearly more efficient in reducing the required time for obtaining optimal makespan of small-size problems, in comparison with the existing MILF. Motivated by relaxing variety of the problem assumptions, several valid lower bounds on the optimal makespan are also proposed that can furtheraccelerate obtaining optimal solution through proposed MILF. Robustness evaluation of each bound under the different problem settings is reported through computations.     

A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan

This paper studies a hybrid flow shop scheduling problem (hybrid FSSP) with multiprocessor tasks, in which a set of independent jobs with distinct processor requirements and processing times must be processed in a k-stage flow shop to minimize the makespan criterion. This problem is known to be strongly nondeterministic polynomial time (NP)-hard, thus providing a challenging area for meta-heuristic approaches. This paper develops a simulated annealing (SA) algorithm in which three decode methods (list scheduling, permutation scheduling, and first-fit method) are used to obtain the objective function value for the problem. Additionally, a new neighborhood mechanism is combined with the proposed SA for generating neighbor solutions. The proposed SA is tested on two benchmark problems from the literature. The results show that the proposed SA is an efficient approach in solving hybrid FSSP with multiprocessor tasks, especially for large problems.     

Two-machine, no-wait job shop problem with separable setup times and single-server constraints

No-wait job shop scheduling problems refer to the set of problems in which a number of jobs are available for processing on a number of machines in a job shop context with the added constraint that there should be no waiting time between consecutive operations of the jobs. In this paper, a two-machine, no-wait job shop problem with separable setup times and a single-server constraint is considered. The considered performance measure is the makespan. This problem is strongly NP-hard. A mathematical model of the problem is developed and a number of propositions are proven for the special cases. Moreover, a genetic algorithm is proposed in this paper to find the optimal (or near-optimal) solutions. In order to evaluate the developed algorithm, a number of small instances are solved to optimality using the developed mathematical model. The proposed algorithm is able to find the optimal solution of all of these cases. For larger instances, the developed algorithm has been compared with the 2-opt algorithm as well as a proposed lower bound. Computational results show the efficiency of the proposed algorithm in generating good quality solutions compared to the developed lower bounds and 2-opt algorithm.     

Combined column generation and constructive heuristic for a proportionate flexible flow shop scheduling

In a proportionate flow shop problem, jobs have to be processed through a fixed sequence of machines, and processing time for each job is equal on all machines. Such a problem has seldom been tackled. Proportionate flexible flow shop (PFFS) scheduling problems combine the properties of proportionate flow shop scheduling problems and parallel machine scheduling problems. This study presents a combined approach based on column generation (CG) for a PFFS problem with the criterion to minimize the objective of the total weighted completion time (TWCT). Minimizing TWCT in a PFFS problem significantly differs from the parallel-identical-machine scheduling problem, an optimal schedule in which jobs on each machine are in the weighted shortest processing time (WSPT) order. This combined approach adopts a CG approach to effectively handle job assignments to machines, and a constructive heuristic to obtain an optimal sequence for a single machine. Experimental results show the effectiveness of the combined approach in obtaining excellent quality solutions in a reasonable time, especially for large-scale problems.     

A new hybrid parallel algorithm for consistent-sized batch splitting job shop scheduling on alternative machines with forbidden intervals

Considering alternative machines for operations, forbidden intervals during which machines cannot be available and a job’s batch size greater than one in the real manufacturing environment, this paper studies the batch splitting scheduling problem on alternative machines with forbidden intervals, based on the objective to minimize the makespan. A scheduling model is established, taking before-arrival set-up, processing, and transfer time into account. And a new hybrid parallel algorithm, based on differential evolution and genetic algorithm, is brought forward to solve both the batch splitting problem and the batch scheduling problem by assuming a common number of sub-batches in advance. A solution consists of the actual optimum number of sub-batches for each job, the optimum batch size for each sub-batch, and the optimum sequence of operations for these sub-batches. Experiments on the performance of the proposed algorithm under different common numbers of sub-batches are carried out. The results of simulations indicate that the algorithm is feasible and efficient.     

A joint GA+DP approach for single burn-in oven scheduling problems with makespan criterion

This research is motivated by the scheduling problem found in the burn-in operation of semiconductor final testing, where jobs are associated with release times, processing times, and sizes. The burn-in ovens are modeled as batch-processing machines which can process a batch of several jobs as long as the total sizes of the jobs do not exceed the machine capacity, and the processing time of a batch is equal to the longest time among all the jobs in the batch. Moreover, this paper attempts to schedule jobs on a single batch-processing machine to minimize makespan. A joint GA+DP algorithm is proposed involving two stages: (1) the formation of job sequence by genetic algorithm operators, and (2) the formation of batches by a dynamic programming algorithm. Computational experiments are given to examine the performance of the proposed algorithm. The experimental results indicate that the joint GA+DP approach has well improved on all instances with respect to solution quality and runtime.     

ACO-based multi-objective scheduling of parallel batch processing machines with advanced process control constraints

This research was motivated by a scheduling problem in the dry strip operations of a semiconductor wafer fabrication facility. The machines were modeled as parallel batch processing machines with incompatible job families and dynamic job arrivals, and constraints on the sequence-dependent setup time and the qual-run requirements of advanced process control. The optimization had multiple objectives, the total weighted tardiness (TWT) and makespan, to consider simultaneously. Since the problem is NP-hard, we used an Ant Colony Optimization (ACO) algorithm to achieve a satisfactory solution in a reasonable computation time. A variety of simulation experiments were run to choose ACO parameter values and to demonstrate the performance of the proposed method. The simulation results showed that the proposed ACO algorithm is superior to the common Apparent Tardiness Cost-Batched Apparent Tardiness Cost rule for minimizing the TWT and makespan. The arrival time distribution and the number of jobs strongly affected the ACO algorithm’s performance.