Abstract
Job shop scheduling problems with setup times arise in many practical situations such as aerospace industries, fabrication industries, printing industries and semiconductor manufacturing industries. This is the first article which provides a comprehensive review of the literature on job shop scheduling research involving setup times. The literature is classified into two broad categories, namely, job shop scheduling problems with non-batch (job) setup times and job shop scheduling problems with batch setup times. The two categories are subcategorized into problems with sequence-dependent setup times and sequence-independent setup times and review the exact, hybrid and heuristic solution methods used for each subcategory. Furthermore, it summarizes the existing research and identifies directions for future research.
Introduction
Production scheduling in the manufacturing system is associated with allocation of a set of jobs on a set of production resources over time to achieve some objectives. The job shop scheduling problem (JSSP) is a combinatorial optimization problem as well as non-deterministic polynomial-time (NP)-hard, and it is one of the most typical and complex among various production scheduling problems.1–4 In a classical JSSP, n-jobs J = {J1, J2, ..., Jn} are processed on m-machines M = {M1, M2, ..., Mm}, and each job has specific operation order. 5 Each job can be processed by at most one machine at a time, and each machine can process at most one operation at a time. Preemption (processing interruption) of jobs is not allowed. There are several variants to classical JSSPs. Dynamic JSSP represents the environment in which jobs arrive continuously over time in a manufacturing system. Furthermore, in stochastic dynamic JSSPs, at least one parameter of the job (release time, processing time/setup time) is probabilistic.6,7 The flexible JSSP is an extension of classical JSSP and consists of two sub-problems: assignment of an operation to an appropriate machine and sequencing the operations on each machine. 8 The flexible JSSP, a more complex version of JSSP, is strongly NP-hard. 2 The common objectives in JSSPs are to minimize some performance measures such as makespan, mean flow time, mean tardiness, number of tardy jobs, mean setup time and mean number of setups.4,5,9–12
JSSPs can be solved by using (1) exact methods, (2) hybrid methods and (3) heuristics. 13 Exact methods such as branch and bound (B&B) approach, dynamic programming (DP) and mixed integer linear programming (MILP) can only solve small-sized scheduling problems. 13 These methods provide optimal solution of the problems but in exponential computational time. 13 B&B algorithm was first proposed by Land and Doig 14 and works on the idea of successive partitioning of the search space. DP solves many smaller sub-problems before arriving at the final complete solution. The basic idea in linear programming is to find the maximum or minimum of a linear objective under linear constraints. When there are not only integer variables but also conventional continuous variables, it is referred as mixed integer programming. In hybrid methods, exact methods are combined with a heuristic to get efficient and quick results. In heuristic methods, the guarantee to find optimal solutions is sacrificed in order to get near optimal solutions in reasonable computational time. Different heuristic methods include greedy algorithm, dispatching rules (scheduling rules) and metaheuristics such as genetic algorithm (GA), simulated annealing (SA), tabu search (TS) and ant colony optimization (ACO). Greedy algorithms successively build solutions according to maximizing locally available improvements. A dispatching rule selects the next job to be processed from the input queue of the machine. Dispatching rules are also termed as sequencing rules or scheduling rules. Holland 15 developed the idea of GAs based on Darwin’s evolution theory. The earliest application of GAs to JSSPs was proposed by Davis. 16 SA mimics the physical evolution of a solid to thermal equilibrium, slowly cooling until it reaches its lower energy state. Kirkpatrick et al. 17 studied first the analogy between this process and an optimization procedure. TS was developed by Glover 18 and has been used earlier in JSSPs by Barnes and Chambers 19 and Taillar. 20 In TS, some solutions that have been examined recently are memorized, and these become tabu (forbidden) points to be avoided in making decisions about selecting the next solution. Ant algorithms were first proposed by Dorigo et al. 21 as a multi-agent heuristic search approach to solve the traveling salesman problem (TSP). Colorni et al. 22 were the first to apply an ant colony algorithm to the JSSPs where a finite-sized colony of artificial ants searches for good quality solutions. Since JSSPs with setup times are NP-hard, exact method cannot be used, and development of heuristics and metaheuristics is required. 23
Setup time is a time which is required to prepare the necessary resources such as machines to perform a task. 24 In many real-life situations, a setup operation often occurs while shifting from one operation to another. Setup activities may include setting the required jigs and fixtures; setting the jobs in jigs and fixtures; obtaining, adjusting and returning tools for an operation; positioning work in process material; cleaning up the machines; and inspection of the material in manufacturing systems. Setup time is classified into two categories, namely, sequence-independent setup time and sequence-dependent setup time. Sequence-independent setup time depends solely on current task regardless of its previous task, for example, a machine shop performing simple machining operations. Sequence-dependent setup time depends on both current and immediately preceding task, for example, chemical industries where extent of cleansing depends on both the chemical most recently processed and the chemical about to be processed. 25 Furthermore, setup times can incur in two modes, that is, non-batch (job) setup times and batch setup times for both sequence-independent and sequence-dependent setup time categories as shown in Figure 1. In non-batch (job) setup time scheduling, setup time is incurred when shifting from one job type to another. A typical example is a machine shop manufacturing the components for aerospace industry. Batch setup time problems occur when job types are grouped into batches and setup time is incurred while shifting from one batch to another. 24 Wafer fabrication in semiconductor industries is an example of JSSP with batch setup times. Setup time plays an important role as reduction in setup time is required to increase the output, competitiveness, profitability and satisfaction in an organization. 24
Classification of job shop scheduling problems with setup times. 26
Ignoring setup times, very small instances of JSSP with two machines and unit processing times can be solved optimally. 27 Lenstra and Rinnooy Kan 23 proved that general JSSP is NP-hard when numbers of machines are greater than three. The NP-hard problems cannot be solved in polynomial time, and computational time for obtaining an optimal solution increases exponentially with increase in problem size. For n-jobs, m-machines JSSP with setup times, maximum number of possible solutions are (n!)m. Thus, even for relatively small-sized problem like 5 × 5, maximum numbers of possible solutions are (5!)5 = 2.4 × 1010. This makes the problem NP-hard in strong sense. Hence, solution of this problem cannot be provided by exact methods. As a result, development of heuristics and metaheuristics become essential. 23
Lawler et al. 28 used standard three-field notation α/β/γ to describe scheduling problems. The first field “α” describes the shop type, the second field “β” describes shop conditions and setup information and the third field “γ” is reserved for performance measures. Table 1 summarizes the various notation used for different job shop types, shop characteristics, setup information and performance measures. Thus, three machine JSSPs to minimize tardiness with batch sequence-dependent setup times will be represented as J3/STsd,b/T.
Notation of α/β/γ representation. 26
The scheduling research in job shop with setup times began in mid-1960s and has grown tremendously in the last few decades.29,30 The JSSPs with setup times are widely studied problems in literature due to applicability of results derived from research into practical environment. 31 Although a few reviews considering scheduling problems with setup times are available,13,26,29 there is no comprehensive review on JSSPs involving setup times. This article is a first attempt in this direction, so that further research can be stimulated in the area of JSSPs involving setup times. This article contributes to the conceptual systemization of material by synthesizing the vast material available on JSSPs involving setup times that will assist a novice to understand the different aspects of it. Furthermore, it will provide a platform that will assist researchers to carry out work in this area. It also identifies possible avenues of future research area. This article classifies the literature into two broad categories, namely, JSSPs with non-batch (job) setup times and JSSPs with batch setup times. Furthermore, each category is subcategorized into problems with sequence-dependent setup times and sequence-independent setup times and reviews the exact, hybrid and heuristic solution methods used for each subcategory. For each subcategory, the authors reviewed the problems focusing on the following aspects: (1) notation of the problem, (2) identifying the manufacturing environment, (3) describing method used to solve the problem, and finally, (4) findings/remarks about the problem. The review of existing literature reveals the potential areas worthy for future research.
The remainder of this article is organized as follows: the next section “JSSPs with non-batch (job) setup times” presents review of literature associated with JSSPs with non-batch (job) setup times. The literature review of JSSPs with batch setup times is presented in section “JSSPs with batch setup times.” Finally, conclusion drawn from this article that identifies important research issues is presented in section “Conclusions and future research directions.”
JSSPs with non-batch (job) setup times
In non-batch (job) JSSPs, an individual job is processed each time. Several researchers have focused their attention toward JSSPs with consideration of non-batch (job) setup times. Their contribution is discussed in the following subsections.
Sequence-dependent non-batch (job) setup times
Numerous researchers have studied JSSPs with sequence-dependent non-batch (job) setup times. The contribution of these researchers is described as per the approach adopted. Table 2 summarizes the work done by various researchers.
Summary of research work in job shop scheduling with sequence-dependent non-batch (job) setup times.
Exact and hybrid methods
Artigues and Feillet
34
proposed a new method for solving J/STsd,j/Cmax. The method is based on iterative solving of decisional version of the problem using B&B approach. At each node of the B&B tree, constraint propagation algorithms are used for domain filtering and feasibility check. To perform additional pruning, relaxations based on traveling salesman problem with time windows (TSPTW) are also solved. The proposed method solves previously unsolved benchmark instances of Brucker and Thiele.
69
Ballicu et al.
35
represented J/STsd,j/C,Cmax,T,Tmax in terms of disjunctive graphs. They developed a MILP model to keep into account the exact order in which operations are performed. They compared the results of MILP approach with the results of general algorithms and dispatching rules, that is, first come first serve (FCFS), shortest processing time (SPT), longest processing time (LPT) and earliest due date (EDD), and observed that the proposed approach provides better solution. Choi and Korkmaz
36
solved J/STsd,j/Cmax through MILP and an efficient heuristic. The procedure is based upon sequentially identifying a pair of operations that provide a minimum lower bound on the makespan of the associated two-jobs/m-machines problem with release times. The computational results of the proposed method are superior to the method of Chen and Pius.
9
Chinyao et al.
37
proposed mathematical modeling for J/STsd,j,RCRC/MFT,MT,MMI. They developed an integer programming model to optimize each objective. They also used global criterion method,
70
a multiple decision-making technique, and applied it to develop a multi-objective model that gives a satisfactory schedule which simultaneously minimizes three performance measures. Gupta
38
addressed J/STsd,j/TSC. They proposed a mathematical model based on B&B method to arrive at an optimal solution of the objective, that is, minimizing the cost of setting up the machines. They concluded that proposed algorithm can solve small-sized problems effectively. Peter et al.
39
proposed a solution methodology based on Lagrangian relaxation technique, DP and heuristic to solve FJ/STsd,j/
The reviewed literature in this section reveals that the researchers have studied JSSPs with sequence-dependent non-batch (job) setup times using exact methods such as B&B algorithm, MILP and DP. Furthermore, maximum number of machines in a shop and number of job types that are taken into consideration are 5 and 20, respectively. There are only two articles that followed hybrid methods to find optimal solution. The maximum number of machines in a shop and number of job types that are taken into consideration are 47 and 80, respectively. Furthermore, articles considered static job shop with deterministic times. One article considers limited capacity buffer between machines, 39 one article considers multi-objective problem, 37 one article considers routing flexiblity, 39 one article considers setup-oriented performance measures 38 and one article considers recirculation of job in a job shop. 37
Heuristic methods
Kim and Bobrowski 6 studied the impact of sequence-dependent setup times on the performance of a stochastic dynamic J/STsd,j/MST,MNS,PTJ,MT,MFT,MWPI,MFGI,MMU,MTCD. They investigated that job with smallest setup time (SIMSET) rule outperforms other scheduling rules when a JSSP with sequence-dependent setup times is considered. Kim and Bobrowski 7 addressed a stochastic dynamic J/STsd,j/MFT,MWPI,MFGI,PTJ,MT,MMU,ATDC with uncertain setup times. They considered setup time variation within-job variation in addition to between-job variation. They concluded that SIMSET rule provides better performance compared with other conventional rules throughout various degree of setup time variation. Chen and Pius 9 studied J/STsd,j/Cmax and proposed a computer-based methodology to integrate the benefits of a scheduling algorithm with the expert knowledge of a human scheduler through a graphic and interactive program to search an optimal solution. Vinod and Sridharan 11 proposed setup-oriented scheduling rules for dynamic J/STsd,j/MFT,MT,MST,MNS. The computational results indicate that setup-oriented scheduling rules provide better performance compared with conventional rules. Moghaddas and Houshmand 31 developed a heuristic model based on priority rules to solve the large-sized problems. The performance of heuristic model indicates the strong ability to solve J/STsd,j/Cmax in reasonable computational times. Artigues et al. 32 proposed a new exact solution algorithm for J/STsd,j/Cmax. They proposed B&B method and investigated a relaxation of the problem related to TSPTW. The B&B approach is used to search a feasible solution while TSPTW relaxation is used to compute an initial lower bound. The proposed approach is found to be competitive to the approach of Focacci et al. 33 Focacci et al. 33 addressed J/STsd,j/Cmax,TST with alternative resources. They proposed two co-operative heuristics for the problem to search an optimal solution. They concluded that co-operation between these two models can effectively be used to minimize the sum of setup times while maintaining the makespan constrained in the given limits.
Artigues and Roubellat 40 extended the online scheduling system presented by Billaut and Roubellat 71 to J/STsd,j/Lmax and multi-resource environment. They proposed Petri nets approach to represent the constraints of scheduling problems, state of the entities to be controlled, event occurring and decisions to be made in a single model. A set of solution generated for an initial static scheduling problem is supposed to be available which acts as input of the proposed decision support system for shop floor scheduling. The system takes account of occurring events to suggest the appropriate scheduling decision and update the solution sets accordingly. Artigues and Roubellat 41 proposed a polynomial insertion algorithm to deal with unforeseen jobs in online J/STsd,j/Lmax with multi-resource requirements. The proposed polynomial insertion algorithm minimizes the maximum lateness while keeping the sequence of the previously scheduled operations unchanged. Artigues et al. 42 defined schedule generation schemes (SGSs) based on semiactive, active and non-delay schedule and evaluated SGSs for J/STsd,j/Cmax. They studied dominance properties of the sets of schedule obtained with each SGS and used SGSs within single-pass and multi-pass priority rule–based heuristics. Artigues et al. 43 provided the synthesis of the methods described in Artigues et al. 32 for J/STsd,j/Cmax. They proposed a simple TS method and used TSPTW relaxation to derive new lower bounds. The proposed approach improves the results of the instances of the Brucker and Thiele. 69 Balas et al. 44 studied variants of JSSP such as release dates, deadlines and sequence-dependent setup times to optimize Cmax. They adapted shifting bottleneck heuristic to the case when sequence-dependent setup times play an important role. This is done by treating the single-machine scheduling problems that arise in the process as TSPTW and solving the latter by an efficient DP algorithm. The results of the proposed method are superior to results of method of Brucker and Thiele. 69
Bagheri and Zandieh 45 proposed variable neighborhood search (VNS) algorithm for multi-objective FJ/STsd,j/Cmax,MT. The computational results of VNS algorithm are superior to GA of Pezzella et al. 72 and parallel variable neighborhood search (PVNS) algorithm of Yazdani et al. 73 Chin 46 developed a more realistic heuristic algorithm for complicated FJ/STsd,j/MFT,MT,MMI considering multiple machines, multiple routing for the job and resources requirement for an operation. The proposed heuristic algorithm provides more realistic solutions in a relatively short period compared with scheduling rules. Cheung and Zhou 47 developed a hybrid algorithm using GA and heuristic rules for J/STsd,j/Cmax. The first operation on each machine is determined using GA, while other operations are decided according to heuristic rules. The hybrid algorithm greatly improves the search efficiency of GA by reducing the size of the solution space from (n!)m to nm. The proposed hybrid algorithm provides better performance compared with the approach proposed by Choi and Korkmaz. 36 Choi and Choi 48 studied the FJ/STsd,j/Cmax with alternative operations. They presented MILP formulation and local search scheme in the context of Cmax minimization. They concluded that the performance of several greedy-based dispatching rules can be substantially increased by the local search scheme. Chiang and Fu 49 proposed a family of approaches to solve J/STsd,j/NTJ. The first member of the family is a critical ratio (CR) dispatching rule. The second member, an enhanced approach, consisting of an iterative schedule refining mechanism is proposed. Finally, the third member GA optimizes the parameters of the enhanced critical ratio (ECR) rule. The performance of the proposed approach is superior to the scheduling rules taken from literature.
Camino et al. 50 proposed a hybrid algorithm called memetic algorithm for J/STsd,j/Cmax. First, they evaluated the problem separately with plain GA and local search starting from random solutions. Later, they combined both methods. The experimental results indicate that the GA combined with local search is much more efficient than either of them applied alone. The results of hybrid algorithm are quite competitive with other approaches of Artigues and Feillet 34 and Balas et al. 44 Fantahun and Mingyuan 51 presented mathematical model of FJ/STsd,j/Cmax incorporating attached or detached setup times, machine release dates and time lag requirements. They proposed parallel genetic algorithm (PGA) for the problem and showed by computational analysis that the PGA outperforms the simple genetic algorithm (SGA). Mohammad and Fattahi 52 studied FJ/STsd,j/Cmax. They proposed TS algorithm which is composed of two parts. The first part searches the best sequence of job operations, while the second part selects the best choice of alternative machines. The proposed algorithm provides better performance compared with B&B algorithm.
Manikas and Chang 53 addressed multi-objective J/STsd,j/E,T,Cmax using GA. The experimental results show that GA outperforms both job-oriented heuristics and machine-oriented heuristics. Manikas and Chang 54 studied multi-objective J/STsd,j/E,T,Cmax and proposed a new metaheuristic called scatter search (SS). The results of SS are compared with other metaheuristics such as TS, SA and GA to prove its reliability. Miguel et al. 55 studied J/STsd,j/Lmax using TS algorithm. They defined a disjunctive model for the problem, which helps to study some properties of the problem. Using these properties, they defined a new local search neighborhood structure, which is incorporated into proposed TS algorithm. The proposed algorithm provides better performance compared with an algorithm proposed by Balas et al. 44 Naderi et al. 56 hybridized the GA (hybrid genetic algorithm (HGA)) with two additional features, a simple form of local search and a diversification mechanism called restart phase, which prevents HGA from becoming stuck in local minima. The HGA outperforms other algorithms proposed by Cheung and Zhou 47 and Zhou et al. 57 for J/STsd,j/Cmax. Zhou et al. 57 solved J/STsd,j/Cmax using biological immune algorithm. They formulated the problem using MILP and proposed immune algorithm to solve the problem. They compared the performance of immune algorithm with DNA method proposed by Fang 74 and observed that optimal solution is greatly improved. Naderi et al. 58 addressed J/STsd,j/Cmax with preventive maintenance policies. They presented two techniques to integrate production scheduling and preventive maintenance. They proposed metaheuristics based on GA and SA to solve the problem. The proposed algorithm outperforms other algorithms proposed by Cheung and Zhou 47 and Zhou et al. 57 Naderi et al. 59 proposed SA approach with novel operators which help in incorporating a novel neighborhood search structure. The proposed algorithm provides better performance compared with other algorithms proposed by Cheung and Zhou, 47 Naderi et al., 56 Zhou et al. 57 and Roshanaei et al. 60 for J/STsd,j/Cmax. Roshanaei et al. 60 proposed a metaheuristic called VNS algorithm for J/STsd,j/Cmax. The proposed algorithm provides better performance compared with other algorithms proposed by Cheung and Zhou, 47 Naderi et al. 56 and Zhou et al. 57
Rossi and Dini 61 presented disjunctive graph representational model of FJ/STsd,j/Cmax incorporating transportation times between machines. They presented an ant colony system (ACS) on disjunctive graph to solve the problem. The proposed system is compared with GA and proves its effectiveness. Sun and Noble 62 developed a new approach called “modified shifting bottleneck approach” based upon Lagrangian relaxation technique and shifting bottleneck approach for J/STsd,j/WMST. The modified shifting bottleneck approach is based on original shifting bottleneck procedure developed by Adam et al. 75 The modified shifting bottleneck approach shows better performance compared with dispatching rules. Sun 63 proposed GA for J/STsd,j,RCRC/Cmax. The different parameters of the GA are optimized using Taguchi approach. A comparative study is conducted, and the results indicate that the proposed GA provides the best solutions within a reasonable computational time. Thürer et al. 64 investigated the influence of sequence-dependent setup times on the performance of a workload controlled (WLC) job shop. They proposed new setup-oriented dispatching rules and assessed the performance impact of controlled order release. The simulation results indicate that combining an effective WLC order release rule with an appropriate dispatching rule improves the performance of the job shop over the use of a dispatching rule in isolation.
Vinod and Sridharan 65 extended their previous work 11 by introducing regression-based metamodel approach for three dispatching rules, namely, SPT, shortest sum of setup time and processing time (SSPT) and job with similar setup and critical ratio (JCR). The metamodel approach provides good results within domain of its definition. Zoghby et al. 66 modeled J/STsd,j,RCRC/Cmax and proposed metaheuristic search methods for the problem. They presented the conditions under which infeasible solutions in scheduling problems occur and developed an algorithm to remove such infeasibilities. Zhang et al. 67 proposed a new method for solving J/STsd,j/Cmax. They modeled the problem with timed Petri nets (TPN) and introduced control arcs on Petri nets to reduce deadlocks. They proposed an efficient B&B algorithm combined with empty syphon checking to find out the optimal deadlock-free schedule. Xuefeng and Ram 68 addressed dynamic FJ/STsd,j/NS,AWT,TH,Cmax,NLJ,AL,MT,ADDD incorporating routing flexibility. They proposed response threshold model (RTM-DS) based on bio-inspired scheduling approach. The RTM-DS approach provides better performance compared with auction-based model (ABM) and dispatching rule–based approach, that is, SPT dispatching rule with most available (MA) routing rule (MA-SPT).
The reviewed literature in this section reveals that researchers have studied JSSPs with sequence-dependent non-batch (job) setup times using TS algorithm, VNS algorithm, GA, HGA, ant colony algorithm, shifting bottleneck heuristic, SA, biological immune algorithm, SS algorithm, TPN algorithm and scheduling rules. Furthermore, maximum number of machines in a shop and number of job types that are taken into consideration are 35 and 100, respectively. The authors considered both static and dynamic JSSPs with deterministic/stochastic times. Three research articles consider multi-objective optimization,45,53,54 two articles consider stochastic problems,6,7 one article considers transportation time between machines, 61 six articles consider routing flexibility,45,46,51,52,61,68 one article considers operation flexibility, 48 four articles consider setup-oriented performance measures,6,11,33,65 two articles consider setup-oriented dispatching rules,11,64 two articles consider recirculation of job in a job shop63,66 and six articles consider dynamic JSSPs.6,7,11,62,65,68
Sequence-independent non-batch (job) setup times
The authors find that a few researchers addressed JSSPs with sequence-independent non-batch (job) setup times. Table 3 summarizes the work done by researchers.
Summary of research work in job shop scheduling with sequence-independent non-batch (job) setup times.
The authors do not find any research article discussing the problems with exact and hybrid methods. Two research articles addressing the problems with heuristics are available. To the best of authors’ knowledge, Wilbrecht and Prescott 30 were first among researchers to study the influence of setup times on job shop performance. They proposed a setup-oriented scheduling rule SIMSET and compared with already existing scheduling rules such as random, EDD, shortest run, shortest process, longest run and longest process for giving priorities to jobs in queues. The rules were tested against 10 performance criteria. The experimental results show that SIMSET rule outperforms other decision rules. Chin 46 simulated JSSP by considering multiple machines, multiple routing for jobs and resources requirement for an operation with sequence-independent setup times in addition to sequence-dependent setup times and no setups to minimize mean flow time, mean tardiness and mean machine idle performance measures. They developed a more realistic heuristic algorithm to solve such complicated problems. The computational analysis indicates that the performance of proposed heuristic algorithm is superior to already existing scheduling rules.
The reviewed literature in this section reveals that researchers have studied the JSSPs with sequence-independent non-batch (job) setup times using simple heuristics and scheduling rules. The maximum number of machines in a shop and number of job types that are taken into consideration are 9 and 25, respectively. Furthermore, the authors considered static job shop with deterministic times. There is one article that considers routing flexibility, 46 and another article considers setup-oriented dispatching rule. 30
JSSPs with batch setup times
A batch is a set of jobs which is processed simultaneously on a machine. A batch may consist of a single job up to n-jobs. Researchers have addressed JSSPs with consideration of batch setup times. Their contribution is discussed in the following subsections.
Sequence-dependent batch setup times
A little research is reported in JSSPs with sequence-dependent batch setup times. Table 4 summarizes the work done by researchers.
Summary of research work in job shop scheduling with sequence-dependent batch setup times.
The authors do not find any research article discussing the JSSP with sequence-dependent batch setup times using exact and hybrid methods. A few articles have addressed the problems with heuristic methods. Fantahun and Mingyuan 76 proposed a lot streaming technique to split production lots into smaller sublots in FJ/STsd,b,BATCH/Cmax. They proposed a PGA for the problem which provides superior performance compared with sequential algorithm. Helen 77 observed that a job batch size also affects the objectives of scheduling problems in addition to operation sequences. They proposed GA approach for J/STsd,b,BATCH/Cmax, in which both operation sequences and batch sizes of jobs are variables. The experimental results indicate that schedule greatly improves if jobs with batch sizes are considered. Hehua and Ming 78 proposed TPN approach to model J/STsd,b,BATCH/Cmax. The TPN approach shows superior performance in batch setup time mode than the case with job setup times. Mehmet et al. 79 addressed J/STsd,b,BATCH/Lmax. They developed heuristic policies based on Markov decision processes (MDP) and showed by computational experiments that the proposed heuristic provides superior performance compared with heuristic policies taken from the literature. 80
The reviewed literature in this section reveals that researchers have studied the JSSPs with sequence-dependent batch setup times using PGA, TPN approach, lot streaming heuristics and other heuristics. The maximum number of machines in a shop and number of job types that are taken into consideration are 21 and 100, respectively. Furthermore, researchers considered static and dynamic shop and deterministic times. There is one article that considers routing flexibility, 76 and another article considers dynamic JSSP. 79
Sequence-independent batch setup times
A few researchers focused their attention toward JSSPs with sequence-independent batch setup times. Table 5 summarizes the work done by various researchers.
Summary of research work in job shop scheduling with sequence-independent batch setup times.
Exact and hybrid methods
The authors find only one article related to this study. Low et al. 81 investigated the benefits of lot splitting in J/STsi,b,BATCH/Cmax,TPC. They described the problem with a disjunctive graph and constructed integer programming model to obtain an optimal solution. A static job shop with maximum six machines that can process maximum six job types with deterministic times is taken into consideration. The computational results show that (1) a batch allocation with equal-sized sublots yields a shorter makespan than a batch allocation with unequal-sized sublots and (2) lot splitting provides a better time benefit than the case without lot splitting the entire batch.
Heuristic methods
Aldakhilallah and Ramesh 82 developed two efficient cyclic scheduling heuristics for J/STsi,b,BATCH,RCRC/BFT,LC. First heuristic considers a repetitive production re-entrant job shop, while the second heuristic is a specialization of the first heuristic that considers anticipatory setup times. The proposed heuristics are efficient and yield superior results. Jeong et al. 83 improved the already existing schedule for J/STsi,b,BATCH/Cmax by splitting the original batch into smaller batch sizes and starting setting up of the machine before actual arrival of the jobs on the machine. They developed an algorithm to split a batch into smaller batches and proposed modified shifting bottleneck heuristic to solve the problem. The proposed heuristics not only generate the better schedules but also calculate the optimal batch size. Rahime and Arslan 84 considered a multi-product, multi-stage lot streaming problem in a stochastic J/STsi,b,BATCH/Cmax,FTS,FTJ,NTS,NTJ incorporating transportation activities. They considered equal and discrete sublot sizes which are also decision variable in addition to job sequencing. They proposed a heuristic algorithm to find the number of equal sublots (NES) for each product type. They analyzed the effects of several transportation queue discipline rules (TRQD) on different shop performance measures. The computational results indicate that some combinations of TRQD and NES alternatives provide superior results.
The reviewed literature in this section reveals that researchers have studied the JSSPs with sequence-independent batch setup times using modified shifting bottleneck heuristic, lot streaming heuristics and other heuristics. The maximum number of machines in a shop and number of job types that are taken into consideration are 10. There is one research article that considers stochastic scheduling problem, 84 two research articles consider transportation time between machines83,84 and one research articles considers recirculation of a job in a job shop. 82
Conclusions and future research directions
This article provides a state
There is a need to address process flexibility, operation flexibility and product flexibility 85 as flexibility has been recognized to improve system performance. There are eight articles that consider routing flexibility in JSSPs with setup times,39,45,46,51,52,61,68,76 and one article considers operation flexibility. 48
There is need to develop setup-oriented dispatching rules. The authors found only three articles that reported development of new setup-oriented dispatching rules.11,30,64
There is a need to assess the impact of buffer size between two successive machines as it has effect on blocking of the machine. All the articles reviewed in research work considered unlimited buffer between two successive machines, except one research article. 39
Majority of reviewed articles considered only JSSPs with non-batch (job) setup times. Limited research is reported in batch mode. Such researches can only be found in eight articles.76–79,81–84 Considering the aspect of scheduling in batch mode and lot sizing may be one of the useful and worthy research areas.
In manufacturing industries, in order to accommodate higher priority jobs or due to machine failure, preemption may occur. This review reveals that this aspect has not been addressed in literature. Therefore, another avenue of research is preemption schedule with setup times.
There is need to assess the impact of transportation time among machines on schedule performance. Inter-machine transportation time has been considered only in three articles.61,83,84
There is need to carry out further research in stochastic job shop with setup times as only three articles have considered this aspect6,7,84 and other reviewed articles have considered deterministic times. This is in line with previous study. 29
In chemical, textile and processing industries, continuous processing of job is required in the presence of setups. None of the reviewed articles has discussed this combined aspect of separable setup times and no-wait processing. Thus, considering JSSPs with no-wait processing and separable setup times may be one of the fertile research areas. This is in line with previous study. 29
There is need to consider setup-related performance measures such as mean setup time and mean number of setups. Majority of reviewed articles considered either flow time or due date–related performance measures. The setup-oriented performance measures are taken into consideration by only five articles.6,11,33,38,65
Only four articles have studied multi-objective JSSPs with setup times.37,45,53,54 Since most of the practical problems are related to multi-objective optimization, so future research solving the JSSPs with setup times to optimize multi-objectives become desirable. This is in line with previous study. 29
Majority of reviewed articles considered static scheduling problems. Dynamic JSSPs in which jobs arrive continuously over time in a manufacturing system have been addressed by seven researchers.6,7,11,62,65,68,79 As dynamic job shop is closer to real-life situation, there is need to consider dynamic job shop in order to increase understanding on this aspect.
In practical JSSPs, recirculation occurs, that is, a job may visit a machine more than once. This aspect needs further investigation as only four researchers have considered this aspect.37,63,66,82
Footnotes
Declaration of Conflicting Interests
The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.
Funding
The author(s) received no financial support for the research, authorship, and/or publication of this article.