Job Shop Scheduling: Classification, Constraints and Objective Functions

Authors: Majid Abdolrazzagh-Nezhad, Salwani Abdullah

Abstract:

The job-shop scheduling problem (JSSP) is an important decision facing those involved in the fields of industry, economics and management. This problem is a class of combinational optimization problem known as the NP-hard problem. JSSPs deal with a set of machines and a set of jobs with various predetermined routes through the machines, where the objective is to assemble a schedule of jobs that minimizes certain criteria such as makespan, maximum lateness, and total weighted tardiness. Over the past several decades, interest in meta-heuristic approaches to address JSSPs has increased due to the ability of these approaches to generate solutions which are better than those generated from heuristics alone. This article provides the classification, constraints and objective functions imposed on JSSPs that are available in the literature.

Keywords: Job-shop scheduling, classification, constraints, objective functions.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1129630

References:

[1] Lageweg, B., Lenstra, J., & Kan, A. H. G. R. (1977). Job-shop scheduling by implicit enumeration. Management Science, 441-450.
[2] Mellor, P. (1966). A review of job shop scheduling. Operations Research, 161-171.
[3] Graves, S. C. (1981). A review of production scheduling. Operations Research, 29(4), 646-675.
[4] Jain, A. S., & Meeran, S. (1999). Deterministic job-shop scheduling: Past, present and future. European Journal of Operational Research, 113(2), 390-434.
[5] Pinedo, M. L. (Ed.). (2012). Scheduling, Theory, Algorithm and Systems. New York: Springer.
[6] Wang, L., Zhou, G., Xu, Y., Wang, S., & Liu, M. (2012). An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 60(1), 303-315.
[7] Moslehi, G., & Mahnam, M. (2011). A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search. International Journal of Production Economics, 129(1), 14-22.
[8] Zhang, G., Gao, L., & Shi, Y. (2011). An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications, 38(4), 3563-3573.
[9] Qiu, X., & Lau, H. Y. (2014). An AIS-based hybrid algorithm for static job shop scheduling problem. Journal of Intelligent Manufacturing, 25(3), 489-503.
[10] Vinod, V., & Sridharan, R. (2011). Simulation modeling and analysis of due-date assignment methods and scheduling decision rules in a dynamic job shop production system. International Journal of Production Economics, 129(1), 127-146.
[11] Adibi, M. A., & Shahrabi, J. (2014). A clustering-based modified variable neighborhood search algorithm for a dynamic job shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 70(9-12), 1955-1961.
[12] Zhang, L., Gao, L., & Li, X. (2013). A hybrid genetic algorithm and tabu search for a multi-objective dynamic job shop scheduling problem. International Journal of Production Research, 51(12), 3516-3531.
[13] Nie, L., Gao, L., Li, P., & Li, X. (2012). A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates. Journal of intelligent Manufacturing, 1-12.
[14] Ahmad, F., & Khan, S. A. (2012). Module-based architecture for a periodic job-shop scheduling problem. Computers & Mathematics with Applications, 64(1), 1-10.
[15] Jamili, A., Shafia, M., & Tavakkoli-Moghaddam, R. (2011(a)). A hybridization of simulated annealing and electromagnetism-like mechanism for a periodic job shop scheduling problem. Expert Systems with Applications, 38(5), 5895-5901.
[16] Brucker, P., Burke, E. K., & Groenemeyer, S. (2012a). A mixed integer programming model for the cyclic job-shop problem with transportation. Discrete applied mathematics, 160(13-14), 1924-1935.
[17] Brucker, P., Burke, E. K., & Groenemeyer, S. (2012b). A branch and bound algorithm for the cyclic job-shop problem with transportation. Computers & Operations Research, 39(12), 3200-3214.
[18] Brucker, P., & Kampmeyer, T. (2008). A general model for cyclic machine scheduling problems. Discrete applied mathematics, 156(13), 2561-2572.
[19] Ebadi, A., & Moslehi, G. (2012). Mathematical models for preemptive shop scheduling problems. Computers & Operations Research, 39(7), 1605-1614.
[20] Schuster, C. J., & Framinan, J. M. (2003). Approximative procedures for no-wait job shop scheduling. Operations Research Letters, 31(4), 308-318.
[21] Baptiste, P., Flamini, M., & Sourd, F. (2008). Lagrangian bounds for just-in-time job-shop scheduling. Computers & Operations Research, 35(3), 906-915.
[22] Zhang, R., & Wu, C. (2010). A hybrid approach to large-scale job shop scheduling. Applied intelligence, 32(1), 47-59.
[23] Topaloglu, S., & Kilincli, G. (2009). A modified shifting bottleneck heuristic for the reentrant job shop scheduling problem with makespan minimization. The International Journal of Advanced Manufacturing Technology, 44(7), 781-794.
[24] Pan, J. C. H., & Chen, J. S. (2005). Mixed binary integer programming formulations for the reentrant job shop scheduling problem. Computers & Operations Research, 32(5), 1197-1212.
[25] Wong, T., & Ngan, S. (2013). A comparison of hybrid genetic algorithm and hybrid particle swarm optimization to minimize makespan for assembly job shop. Applied Soft Computing, 13(3), 1391-1399.
[26] Wong, T., Chan, F. T. S., & Chan, L. (2009). A resource-constrained assembly job shop scheduling problem with Lot Streaming technique. Computers & industrial engineering, 57(3), 983-995.
[27] Gu, J., Gu, M., Cao, C., & Gu, X. (2010). A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem. Computers & Operations Research, 37(5), 927-937.
[28] Lei, D. (2012). Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling. Applied Soft Computing, 12(8), 2237-2245.
[29] Kuroda, M., & Wang, Z. (1996). Fuzzy job shop scheduling. International Journal of Production Economics, 44(1), 45-51.
[30] French, S. (1982). Sequencing and scheduling: an introduction to the mathematics of the job-shop: Ellis Horwood Chichester.
[31] Brucker, P., & Schlie, R. (1990). Job-shop scheduling with multi-purpose machines. Computing, 45(4), 369-375.
[32] Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M., & Sassani, F. (2009). Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Computers & Operations Research, 36(12), 3224-3230.
[33] Kis, T. (2003). Job-shop scheduling with processing alternatives. European Journal of Operational Research, 151(2), 307-332.
[34] Dauzere-Peres, S., Roux, W., & Lasserre, J. (1998). Multi-resource shop scheduling with resource flexibility. European Journal of Operational Research, 107(2), 289-305.
[35] Wang, J. B., & Xia, Z. Q. (2005). Scheduling jobs under decreasing linear deterioration. Information Processing Letters, 94(2), 63-69.
[36] Li, J. Q., & Pan, Q. (2012). Chemical-reaction optimization for flexible job-shop scheduling problems with maintenance activity. Applied Soft Computing, 12(9), 2896-2912.
[37] Bagheri, A., & Zandieh, M. (2011). Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—Variable neighborhood search approach. Journal of Manufacturing Systems, 30(1), 8-15.
[38] Balas, E., Simonetti, N., & Vazacopoulos, A. (2008). Job shop scheduling with setup times, deadlines and precedence constraints. Journal of Scheduling, 11(4), 253-262.
[39] Zribi, N., El Kamel, A., & Borne, P. (2008). Minimizing the makespan for the MPM job-shop with availability constraints. International Journal of Production Economics, 112(1), 151-160.
[40] Fattahi, P., & Saidi, M. M. (2009(a)). A New Approach in Job Shop Scheduling: Overlapping Operation. Journal of Industrial Engineering.
[41] Jansen, K., Mastrolilli, M., & Solis-Oba, R. (2005). Approximation schemes for job shop scheduling problems with controllable processing times. European Journal of Operational Research, 167(2), 297-319.
[42] Abdolrazzagh-Nezhad, M., & Abdullah, S. (2014). A Robust Intelligent Construction Procedure for Job-Shop Scheduling. Information Technology And Control, 43(3), 217-229.
[43] Schulz, A. (1996). Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. Integer Programming and Combinatorial Optimization, 301-315.
[44] McMahon, G., & Florian, M. (1975). On scheduling with ready times and due dates to minimize maximum lateness. Operations Research, 23(3), 475-482.
[45] Zhang, R., & Wu, C. (2011). A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective. Computers & Operations Research, 38(5), 854-867.
[46] Chiang, T.-C., & Fu, L.-C. (2008). A rule-centric memetic algorithm to minimize the number of tardy jobs in the job shop. International Journal of Production Research, 46(24), 6913-6931.
[47] Sevaux, M., & Dauzere-Peres, S. (2003). Genetic algorithms to minimize the weighted number of late jobs on a single machine. European Journal of Operational Research, 151(2), 296-306.