Open Access Open Access  Restricted Access Subscription or Fee Access

Job Shop and Flexible Job Shop Scheduling Problems: Critical Analysis of Literature Review and their Basic Technology

Ajay Kumar Agarwal, Dr. Rakesh Kumar

Abstract


The job shop scheduling problems (JSSPs) is a significant decision point in a production scheduling problem for those who are concerned with the fields of industry, economics in addition to management. This kind of problem is a class of combinational optimization problem which is known as the NP-hard problem. JSSPs deal amid a set of machines and a set of jobs with a variety of predetermined routes through the machines, where the objective is to assemble a schedule of jobs that diminishes the certain criterion such as make span, total weighted completion time, maximum lateness, and total weighted tardiness. Over the precedent several decades, curiosity in meta-heuristic approaches, advancement of heuristic approaches, to address JSSPs has augmented due to the knack of these approaches to breed feasible resolutions which are superior to those breezed from heuristics algorithms independently. This article presents the classification, constraints and objective functions requisite on JSSPs that are accessible in the literature review.

Keywords


Job-Shop Scheduling; NP-hard Problem; Minimization of Make span-Total Weighted Completion Time-Maximum Lateness-Total Weighted Tardiness; Classification-Constraints-Objective Functions of JSSPs

Full Text:

PDF

References


Abdallah, I. B.; H. A. Elmaraghy and T. Elmekkawy (2002). "Deadlock-free scheduling in flexible manufacturing systems using Petri nets." International Journal of Production Research, 40(12): 2733–2756.

Abdolrazzagh-Nezhad, M. & Abdullah, S. (2014). A Robust Intelligent Construction Procedure for Job-Shop Scheduling. Information Technology and Control, 43(3), 217–229.

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.

Adibi, M. A.; M. Zandieh and M. Amiri (2010). "Multi-objective scheduling of dynamic job shop using variable neighborhood search." Expert Systems with Applications 37(1): 282–287.

Ahmad, F. & Khan, S. A. (2012). Module-based architecture for a periodic job-shop scheduling problem. Computers & Mathematics with Applications, 64(1), 1–10.

Al-Hinai, N. and T. Y. ElMekkawy (2011). "An efficient hybridized genetic algorithm architecture for the flexible job shop scheduling problem." Flexible Services and Manufacturing Journal 23 (1): 64–85.

Amiri M., Zandieh M., Yazdani M., Bagher A. (2010), “A variable neighbourhood search algorithm for the flexible job-shop scheduling problem”, International Journal of Production Research, 48, 5671–5689.

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.

Bagheri, A.; M. Zandieh; I. Mahdavi and M. Yazdani (2010). "An artificial immune algorithm for the flexible job-shop scheduling problem." Future Generation Computer Systems 26(4): 533–541.

Balas, E.; Simonetti, N. & Vazacopoulos, A. (2008). Job shop scheduling with setup times, deadlines and precedence constraints. Journal of Scheduling, 11(4), 253–262.

Baptiste, P.; Flamini, M. & Sourd, F. (2008). Lagrangian bounds for just-in-time job-shop scheduling. Computers & Operations Research, 35(3), 906–915.

Ben Hmida, A., M. Haouari, M. J. Huguet and P. Lopez (2010). "Discrepancy search for the flexible job shop scheduling problem." Computers & Operations Research 37(12): 2192–2201.

Bozejko, W.; M. Uchronski and M. Wodecki (2010). "Parallel hybrid metaheuristics for the flexible job shop problem." Computers and Industrial Engineering 59(2): 323–333.

Brandimarte, P. (1993). "Routing and scheduling in a flexible job shop by tabu search." Annals of Operations Research 41(1–4): 157–183.

Brandimarte, P. (1999). "Exploiting process plan flexibility in production scheduling: multiobjective approach." European Journal of Operational Research 114(1): 59–71.

Brucker, P. &Kampmeyer, T. (2008). A general model for cyclic machine scheduling problems. Discrete applied mathematics, 156(13), 2561–2572.

Brucker, P. &Schlie, R. (1990). Job-shop scheduling with multi-purpose machines. Computing, 45(4), 369–375.

Brucker, P. and J. Neyer (1998). "Tabu-search for the multi-mode job-shop problem." OR Spektrum 20(1): 21–28.

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.

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.

Chen J.C., Cheng-Chun Wu C., Chen C., Chen K. (2012), “Flexible job shop scheduling with parallel machines using genetic algorithm and grouping genetic algorithm”, Expert Systems with Applications, 39, 10016–10021.

Chen, H.; J. Ihlow and C. Lehmann (1999). A genetic algorithm for flexible job-shop scheduling. Proceedings of International Conference on Robotics and Automation, 10–15 May 1999, Piscataway, NJ, USA, IEEE.

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.

Choi, I.-C. and D.-S. Choi (2002). "A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups." Computers and Industrial Engineering 42(1): 43–58.

Dauzere-Peres, S. and J. Paulli (1997). "An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search." Annals of Operations Research 70: 281–306.

Dauzere-Peres, S.; W. Roux and J. B. Lasserre (1998). Multi-resource shop scheduling with resource flexibility.

Project Management and Scheduling: Fifth International Workshop, 11–13 April 1996, Netherlands, Elsevier.

De Giovanni, L. and F. Pezzella (2010). "An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem." European Journal of Operational Research 200(2): 395–408.

Ebadi, A. &Moslehi, G. (2012). Mathematical models for preemptive shop scheduling problems. Computers & Operations Research, 39(7), 1605–1614.

ElMaraghy, H. A. (2005). Flexible and reconfigurable manufacturing systems paradigms. Reconfigurable Manufacturing Systems, Kluwer Academic Publishers.

Fattahi, P. &Saidi, M. M. (2009(a)). A New Approach in Job Shop Scheduling:

Overlapping Operation. Journal of Industrial Engineering.

Fattahi, P.; F. Jolai and J. Arkat (2009). "Flexible job shop scheduling with overlapping in operations." Applied Mathematical Modelling 33(7): 3076–3087.

Fattahi, P.; M. S. Mehrabad and F. Jolai (2007). "Mathematical modeling and heuristic approaches to flexible job shop scheduling problems." Journal of Intelligent Manufacturing 18(3): 331–342.

French, S. (1982). Sequencing and scheduling: an introduction to the mathematics of the job-shop: Ellis HorwoodChichester.

Gao, J.; L. Sun and M. Gen (2008). "A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems." Computers and Operations Research 35(9): 2892–2907.

Gao, J.; M. Gen and L. Sun (2006). "Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm." Journal of Intelligent Manufacturing 17(4): 493–507.

Garey, M. R.; Johnson, D. S. and R. Sethi (1976). "The complexity of flowshop and Jobshop scheduling." Mathematics of Operations Research 1(2): 117–129.

Garey, M. R.; Johnson, D. S. and Stockmeyer, L. (1976). Some simplified np-complete graph problems. In Theoretical computer science, 1(3), 237–267.

Girish, B. S. and N. Jawahar (2009). A particle swarm optimization algorithm for flexible job shop scheduling problem. 2009 IEEE International Conference on Automation Science and Engineering (CASE 2009), 22–25 Aug. 2009, Piscataway, NJ, USA, IEEE.

Gomes, M. C.; A. P. Barbosa-Povoa and A. Q. Novais (2005). "Optimal scheduling for flexible job shop operation." International Journal of Production Research 43(11): 2323–2353.

Graves, S. C. (1981). A review of production scheduling. Operations Research, 29(4), 646–675.

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.

Gutierrez, C. and I. Garcia-Magarino (2011). "Modular design of a hybrid genetic algorithm for a flexible job-shop scheduling problem." Knowledge-Based Systems 24(1):

–112.

Habib S., Rahmati A., Zandieh M. (2012), “A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem”, International Journal of Advanced Manufacturing Technology, 58, 1115–1129.

Ho, N. B. and J. C. Tay (2004). GENACE: an efficient cultural algorithm for solving the flexible jobshop problem. Proceedings of the 2004 Congress on Evolutionary Computation, 19–23 June 2004, Piscataway, NJ, USA, IEEE.

Ho, N. B.; J. C. Tay and E. M. K. Lai (2007). "An effective architecture for learning and evolving flexible job-shop schedules." European Journal of Operational Research 179(2): 316–333.

Hurink, J.; B. Jurisch and M. Thole (1994). "Tabu search for the job-shop scheduling problem with multi-purpose machines." OR Spektrum 15(4): 205–215.

Hussain, M. F. and S. B. Joshi (1998). A genetic algorithm for job shop scheduling problems with alternate routing. SMC '98 Conference Proceedings. 1998 IEEE International Conference on Systems, Man, and Cybernetics, 11–14 Oct. 1998, New York, NY, USA, IEEE.

Ida K., Oka K. (2009), “Flexible job-shop scheduling problem by genetic algorithm”, IEEJ Transactions on Electronics Information and Systems, 129(3), 505–511.

Jain, A. S. &Meeran, S. (1999). Deterministic job-shop scheduling: Past, present and future. European Journal of Operational Research, 113(2), 390–434.

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.

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.

Kacem, I.; Hammadi, S. and Borne, P. (2002). Approach by Localization and Multi-objective Evolutionary Optimization for Flexible Job-Shop Scheduling Problems. IEEE

Transactions on Systems, Man, and Cybernetics. Part C, 2002, Vol 32. N1, pp 1–13.

Kacem, I.; Hammadi, S. and Borne, P. (2002). Lower bounds for evaluating schedule performances in flexible job shops. Performance Metrics for Intelligent Systems Workshop, PerMIS'02, Gaithersburg, MD, 2002. USA.

Kacem, I.; Hammadi, S. and Borne, P. (2002). Pareto-optimality Approach for Flexible Job-shop Scheduling Problems: Hybridization of Evolutionary Algorithms and Fuzzy Logic. Journal of Mathematics and Computers in Simulation, Elsevier.

Kis, T. (2003). Job-shop scheduling with processing alternatives. European Journal of Operational Research, 151(2), 307–332.

Kuroda, M. and Wang, Z. (1996). Fuzzy job-shop scheduling. International Journal of Production Economics, 44(1), 45–51.

Lageweg, B.; Lenstra, J. &Kan, A. H. G. R. (1977). Job-shop scheduling by implicit enumeration. Management

Science, 441–450.

Lee S., Moon I., Bae H., Kim J. (2012), “Flexible job-shop scheduling problems with AND/OR precedence constraints”, International Journal of Production Research, 50, 1979–2001.

Lei, D. (2012). Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling. Applied Soft Computing, 12(8), 2237–2245.

Li J., Pan Q., Chen J. (2012), “A hybrid Pareto-based local search algorithm for multi-objective flexible job shop scheduling problems”, International Journal of Production Research, 50, 1063–1078.

Li J., Pan Q., Suganthan P., Chua T. (2011), “A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem”, International Journal of Advanced Manufacturing Technology, 52, 683–697.

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.

McMahon, G. & Florian, M. (1975). On scheduling with ready times and due dates to minimize maximum lateness. Operations Research, 23(3), 475–482.

Mellor, P. (1966). A review of job shop scheduling. Operations Research, 161–171.

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.

Nie, L.; Gao, L.; Li, P. & Li, X. (2013). A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates. Journal of intelligent Manufacturing, 763–774.

Pinedo, M. L. (Ed.). (2012). Scheduling, Theory, Algorithm and Systems. New York: Springer.

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.

Rajkumar M., Asokan P., Anilkumar N., Page T. (2011), “A GRASP algorithm for flexible job-shop scheduling problem with limited resource constraints”, International Journal of Production Research, 49, 2409–2423.

Rajkumar M., Asokan P., Vamsikrishna V. (2010), “A GRASP algorithm for flexible job-shop scheduling with maintenance constraints”, International Journal of Production Research, 48, 6821–6836.

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.

Schuster, C. J. &Framinan, J. M. (2003). Approximative procedures for no-wait job-shop scheduling. Operations Research Letters, 31(4), 308–318.

Shi-Jin W., Bing-Hai Z., Li-Feng X. (2008), “A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem”, International Journal of Production Research, 46, 3027–3058.

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.

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.

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.

Wang, J. B. & Xia, Z. Q. (2005). Scheduling jobs under decreasing linear deterioration. Information Processing Letters, 94(2), 63–69.

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.

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.

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.

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.

Zhang, R. & Wu, C. (2010). A hybrid approach to large-scale job shop scheduling. Applied intelligence, 32(1), 47–59.

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.

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.




DOI: https://doi.org/10.37628/ijied.v6i1.1092

Refbacks

  • There are currently no refbacks.