Abstract
In practice, parallel-machine job-shop scheduling (PMJSS) is very useful in the development of standard modelling approaches and generic solution techniques for many real-world scheduling problems. In this paper, based on the analysis of structural properties in an extended disjunctive graph model, a hybrid shifting bottleneck procedure (HSBP) algorithm combined with Tabu Search (TS) metaheuristic algorithm is developed to deal with the PMJSS problem. The original-version shifting bottleneck procedure (SBP) algorithm for the job-shop scheduling (JSS) has been significantly improved to solve the PMJSS problem with four novelties: (i) a topological-sequence algorithm is proposed to decompose the PMJSS problem in a set of single-machine scheduling (SMS) and/or parallel-machine scheduling subproblems; (ii) a modified Carlier algorithm based on the proposed lemmas and the proofs is developed to solve the SMS subproblem; (iii) the Jackson rule is extended to solve the PMS subproblem; (iv) a TS metaheuristic algorithm is embedded under the framework of SBP to optimise the JSS and PMJSS cases. The computational experiments show that the proposed HSBP is very efficient in solving the JSS and PMJSS problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adams J, Balas E and Zawack D (1988). The shifting bottleneck procedure for job shop scheduling. Manage Sci 34 (3): 391–401.
Alvarez-Valdes R, Fuertes A, Tamarit JM, Giménez G and Ramos R (2005). A heuristic to schedule flexible job-shop in a glass factory. Eur J Opnl Res 165: 525–534.
Balas W and Vazacopoulos A (1998). Guided local search with shifting bottleneck for job shop scheduling. Manage Sci 44: 262–275.
Carlier J (1982). The one-machine sequencing problem. Eu J Opnl Res 11: 42–47.
Chen H and Luh PB (2003). An alternative framework to Lagrangian relaxation approach for job shop scheduling. Eur J Opnl Res 149: 499–512.
Cheng J, Karuno Y and Kise H (2001). A shifting bottleneck approach for a parallel-machine flowshop scheduling problem. J Opns Res Soc Jpn 44 (2): 140–155.
Dauzère-Pérès S and Paulli J (1997). An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Ann Opns Res 70: 281–306.
Fattahi P, Mehrabad MS and Jolai F (2007). Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J Intell Manuf 18: 331–342.
Gao J, Sun L and Gen M (2008). A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Comput Opns Res 35: 2892–2907.
Huang WQ and Yin AH (2004). An improved shifting bottleneck procedure for the job shop scheduling problem. Comput Opns Res 31: 2093–2110.
Ivens P and Lambrecht M (1996). Extending the shifting bottleneck procedure to real-life applications. Eur J Opnl Res 90: 252–268.
Kellerer H (2005). Minimizing the maximum lateness. In: Leung JY-T (ed). Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapter 10. Chapman & Hall/CRC: USA.
Liu SQ and Kozan E (2009). Scheduling trains as a blocking parallel-machine job shop scheduling problem. Comput Opns Res 36: 2840–2852.
Liu SQ and Kozan E (2011). Scheduling trains with priorities: A no-wait blocking parallel-machine job-shop scheduling model. Transport Sci 45: 175–198.
Liu SQ and Ong HL (2004). Metaheuristics for the mixed shop scheduling problem. Asia Pac J Opnl Res 21 (4): 97–115.
Liu SQ, Ong HL and Ng KM (2005). A fast tabu search algorithm for the group shop scheduling problem. Adv Eng Softw 36: 533–539.
Mason SJ, Fowler JW and Carlyle WM (2002). A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops. J Sched 5 (3): 247–262.
Mönch L and Drießel R (2005). A distributed shifting bottleneck heuristic for complex job shops. Comput Ind Eng 49: 363–380.
Mönch L, Schabacker R, Pabst D and Fowler JW (2007). Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops. Eur J Opnl Res 177: 2100–2118.
Pfund ME, Balasubramanian H, Fowler JW, Mason SJ and Rose O (2008). A multi-criteria approach for scheduling semiconductor wafer fabrication facilities. J Sched 11 (1): 29–47.
Ramudhin A and Marier P (1996). The generalized shifting bottleneck procedure. Eur J Opnl Res 93: 34–48.
Sadeh N, Sycara K and Xiong Y (1995). Backtracking techniques for the job shop scheduling constraint satisfaction problem. Artif Intell 76: 455–480.
Xia W and Wu Z (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Comput Ind Eng 48: 409–425.
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix A
Using a numerical example, Appendix A presents a proof that Theorem 2 proposed by Carlier (1982) may be incorrect. The data of a 2-job SMS example with different release times and delivery times is given in Table A1.
To enumerate all the solutions of this 2-job SMS example, the DDGs and the Gantt charts are drawn in Figure A1.
The DDGs and Gantt charts for a 2-job SMS example.
From Figure A1, it is evident that the optimal makespan is 28 and the optimal SMS sequence is {J 1, J 2}.
If {J 1, J 2} is a Schrage schedule, then we have a critical path {F, a, a+1, …, c, L}={F, 1, 2, L}, critical sequence Λ={1, 2}, interference job w=1 as q 1<q 2, critical subset Λ w ={2} and the makespan equal to 28.
According to Theorem 1 proposed by Carlier (1982), the value of h(Λ w ) for this Schrage schedule is calculated as below:
As this Schrage schedule is optimal, it is contradicted to Carlier's Theorem 2 because h(Λ w ) equals 27 and the makespan (C max) of this schedule is 28, that is h(Λ w )≠C max in this case.
Moreover, for all possible sets of jobs (ie {2}, {1}, {1, 2}, {2, 1}), we obtain
Obviously, there is no possibility of having a subset of jobs to satisfy Theorem 2 proposed by Carlier (1982).
Appendix B
The proof for the proposed Lemmas I and II is given in Appendix B. For any subset A∈J of jobs, the inequality is certain, thus we have
Assume A=Λ and Λ={a, a+1, …, c}, we obtain,
due to 
and there is no idle time between the processing of jobs a and c.
In addition, it is certain that,
where e a is the starting time of job a. As e a ≡r a , we obtain,
Therefore, 
Appendix C
The proposed Lemma III is similar to Theorem 1 proposed by Carlier (1982). To complete analysing the properties of the Schrage schedule, here we present our own proof that is different from Carlier's proof.
As Λ w ={w+1, …, c} is the subset of jobs processed after the interference job w, it is clear that q w <q c ⩽q j and e w <r j hold for all j∈Λ w , where e w is the starting time of the interference job w. Hence, inequality applied to Λ w ={w+1, …, c} generates another lower bound:
Since there is no idle time during the execution of the jobs in the critical sequence, the makespan of the Schrage schedule is 
.
Because 
, we obtain
Appendix D
To verify the proposed Lemmas IV and V, a 7-job SMS example with different release times and delivery times introduced by Carlier (1982), is used for the following computational experiments. The data of this 7-job SMS example with different release times and delivery times is given in Table A2.
The following computational results will prove Lemmas IV and V.
Step 1: After applying Schrage algorithm to this instance, the initial schedule is obtained and displayed in Table A3 and the makespan (ie the maximum completion-delivery time) can be obtained by
Step 2: As the interference job w (Job 1) should be processed after the critical subset Λ w ={2, 3, 4}, the release date of Job 1 is updated by:
After applying Schrage algorithm, a new Schrage solution is found and displayed in Table A4.
It is further observed from Table A4 that
Step 3: As the interference job w (job 3) should be processed after the critical subset Λw={2}, we reset the release date of Job 3 by:
After reapplying the Schrage algorithm, a new Schrage solution is obtained and displayed in Table A5.
Lemma IV, ‘for a Schrage schedule, 
exists’, is verified again by the fact that:
Note that the current schedule satisfies 
for all j∈Λ but its makespan is 51 that is not optimal. As a matter of fact, the optimal makespan is 50 with q
3<q
2, q
2=q
c
and Λ={J3, J2}. Therefore, Lemma V (‘Even if 
, this Schrage schedule may not be optimal’) is proved. Lemma V indicates that the stopping condition (ie ‘Schrage schedule is optimal if 
, ∀j∈Λ’) introduced in the book (Kellerer 2005) may be incorrect or incomplete. This is the main reason why we propose a modified Carlier algorithm for solving the SMS problem with different release times and delivery times.
Rights and permissions
About this article
Cite this article
Liu, S., Kozan, E. A hybrid shifting bottleneck procedure algorithm for the parallel-machine job-shop scheduling problem. J Oper Res Soc 63, 168–182 (2012). https://doi.org/10.1057/jors.2011.4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2011.4