Minimizing the maximum tardiness and makespan criteria in a job shop scheduling problem with sequence dependent setup times

Document Type : Research Paper

Authors

School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

Abstract

The job shop scheduling problem (JSP) is one of the most difficult problems in traditional scheduling because any job consists of a set operations and also any operation processes by a machine. Whereas the operation is placed in the machine, it is essential to be considering setup times that the times strongly depend on the various sequencing of jobs on the machines. This research is developed a two-objective model to solve JSP with sequence-dependent setup times (SDST). Considering SDST and optimizing of the both objectives simultaneously (makespan and maximum tardiness) bring us closer to natural-world problems. The ε-constraint method is applied to solve the mentioned two-objective model. A set of numerical data is generated and tested to validate the model’s efficiency and flexibility. The developed model can efficiently use for solving JSPs in the real world, especially for manufacturing companies with having setup and delivery time’s constraints.

Keywords

Main Subjects

References

Al-Hinai, N. and T. Y. ElMekkawy (2011a). An efficient hybridized genetic algorithm architecture for the flexible job shop scheduling problem. Flexible Services and Manufacturing Journal 23(1): 64-85.
Al-Hinai, N. and T. Y. ElMekkawy (2011b). Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm. International Journal of Production Economics 132(2): 279-291.
Asano, M. and H. Ohta (2002). A heuristic for job shop scheduling to minimize total weighted tardiness. Computers & Industrial Engineering 42(2–4): 137-147.
Bagheri, A. and M. Zandieh (2011). Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—variable neighborhood search approach. Journal of Manufacturing Systems 30(1): 8-15.
Brucker, P., et al. (1994). A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics 49(1–3): 107-127.
Carlier, J. and E. Pinson (1989). An Algorithm for Solving the Job-Shop Problem. Management Science 35(2): 164-176.
Della Croce, F., et al. (1995). A genetic algorithm for the job shop problem. Computers & Operations Research 22(1): 15-24.
Ebadi, A. and G. Moslehi (2013). An optimal method for the preemptive job shop scheduling problem. Computers & Operations Research 40(5): 1314-1327.
Fattahi, P. and F. Daneshamooz (2017). Hybrid algorithms for Job shop Scheduling Problem with Lot streaming and A Parallel Assembly Stage. Journal of Industrial and Systems Engineering 10(3): 92-112.
Fattahi, P., et al. (2007). Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of Intelligent Manufacturing 18(3): 331-342.
Garey, M. R., et al. (1976). The Complexity of Flowshop and Jobshop Scheduling. Mathematics of Operations Research 1(2): 117-129.
Gonçalves, J. F., et al. (2005). A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research 167(1): 77-95.
González, M. A., et al. (2013). Lateness minimization with Tabu search for job shop scheduling problem with sequence dependent setup times. Journal of Intelligent Manufacturing 24(4): 741-754.
Kim, S. and P. Bobrowski (1994). Impact of sequence-dependent setup time on job shop scheduling performance. The International Journal of Production Research 32(7): 1503-1520.
Kuhpfahl, J. and C. Bierwirth (2016). A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective. Computers & Operations Research 66: 44-57.
Kurdi, M. (2016). An effective new island model genetic algorithm for job shop scheduling problem. Computers & Operations Research 67: 132-142.
Laarhoven, P. J. M. v., et al. (1992). Job Shop Scheduling by Simulated Annealing. Operations Research 40(1): 113-125.
Lee, Y. H. and M. Pinedo (1997). Scheduling jobs on parallel machines with sequence-dependent setup times. European Journal of Operational Research 100(3): 464-474.
Li, J.-Q., et al. (2014). A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Applied Mathematical Modelling 38(3): 1111-1132.
Mattfeld, D. C. and C. Bierwirth (2004). An efficient genetic algorithm for job shop scheduling with tardiness objectives. European Journal of Operational Research 155(3): 616-630.
Mousakhani, M. (2013). Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness. International journal of production research 51(12): 3476-3487.
Naderi, B. and A. Azab (2014). Modeling and heuristics for scheduling of distributed job shops. Expert Systems with Applications 41(17): 7754-7763.
Naderi, B., et al. (2009). Scheduling job shop problems with sequence-dependent setup times. International journal of production research 47(21): 5959-5976.
Naderi, B., et al. (2009). Scheduling sequence-dependent setup time job shops with preventive maintenance. The International Journal of Advanced Manufacturing Technology 43(1): 170-181.
Nowicki, E. and C. Smutnicki (1996). A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science 42(6): 797-813.
Özgüven, C., et al. (2012). Mixed integer goal programming models for the flexible job-shop scheduling problems with separable and non-separable sequence dependent setup times. Applied Mathematical Modelling 36(2): 846-858.
Park, B. J., et al. (2003). A hybrid genetic algorithm for the job shop scheduling problems. Computers & Industrial Engineering 45(4): 597-613.
Petrovic, S., et al. (2008). Fuzzy job shop scheduling with lot-sizing. Annals of Operations Research 159(1): 275-292.
Pinedo (2012). Scheduling: theory, algorithms, and systems, Springer Science & Business Media.
Pinedo and M. Singer (1999). A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. Naval Research Logistics 46(1): 1-17.
Ponnambalam, G. S., et al. (2000). A Tabu Search Algorithm for Job Shop Scheduling. The International Journal of Advanced Manufacturing Technology 16(10): 765-771.
Qi, G. J., et al. (2000). The Application of Parallel Multipopulation Genetic Algorithms to Dynamic Job-Shop Scheduling. The International Journal of Advanced Manufacturing Technology 16(8): 609-615.
Saidi-Mehrabad, M. and P. Fattahi (2007). Flexible job shop scheduling with tabu search algorithms. The International Journal of Advanced Manufacturing Technology 32(5): 563-570.
Sharma, P. and A. Jain (2015). Performance analysis of dispatching rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times: Simulation approach. CIRP Journal of Manufacturing Science and Technology 10: 110-119.
Shen, L., et al. (2017). Solving the Flexible Job Shop Scheduling Problem with Sequence-Dependent Setup Times. European Journal of Operational Research.
Sun, X. and J. S. Noble (1999). An approach to job shop scheduling with sequence-dependent setups. Journal of Manufacturing Systems 18(6): 416-430.
Taillard, E. D. (1994). Parallel Taboo Search Techniques for the Job Shop Scheduling Problem. ORSA Journal on Computing 6(2): 108-117.
Tan, et al. (2015). Configuration and the advantages of the shifting bottleneck procedure for optimizing the job shop total weighted tardiness scheduling problem. Journal of scheduling: 1-24.
Watanabe, M., et al. (2005). A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem. Computers & Industrial Engineering 48(4): 743-752.
Yang, S., et al. (2010). An improved constraint satisfaction adaptive neural network for job-shop scheduling. Journal of scheduling 13(1): 17-38.
Zhang, et al. (2007). A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Computers & Operations Research 34(11): 3229-3242.
Zhang, et al. (2008). A very fast TS/SA algorithm for the job shop scheduling problem. Computers & Operations Research 35(1): 282-294.
Zhang, et al. (2012). A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times. Computers & Operations Research 39(7): 1713-1723.
Journal of Industrial and Systems Engineering
Volume 11, Issue 2
April 2018
Pages 134-150

Files

History

  • Receive Date: 03 October 2017
  • Revise Date: 09 January 2018
  • Accept Date: 27 January 2018

Share

How to cite

Statistics