Job Shop Scheduling: History
View Latest Version
Please note this is an old version of this entry, which may differ significantly from the current revision.
Subjects: Engineering, Industrial
Contributor:
Raja Awais Liaqait

Job shop scheduling is one of the most frequently used types of scheduling in manufacturing facilities. In recent years, various research has been conducted to analyze the integration and impacts of the Industry 4.0 environment on job shop scheduling.

  • smart distributed system
  • job shop scheduling
  • Industry 4.0
  • smart factory
  • flexible job shop scheduling

1. Introduction

JSSP includes job operations with different machine sequences that have different processing times. [1] classified JSSP as an NP-hard optimization problem where different machines are assigned to various jobs while minimizing any of the applicable predefined criteria. Therefore, researchers and practitioners have gradually shifted their focus from traditional scheduling arrangement to smart-distributed scheduling (SDS) aided with technological pillars of the Industry 4.0 environment, such as Cyber-Physical Systems (CPS), Big data, Artificial Intelligence (AI), Internet of Things (IoTs), and Social, Mobile, Analytics, Cloud computing (SMAC). The transition from traditional scheduling to SDS faces two major research challenges: the integration of conventional JSSP scheduling techniques with SDS, and the development of new problem-solving techniques required for SDS.

Various models for JSSP have been proposed for improving the operational efficiency of a job shop production facility. A detailed review of the literature reveals that several studies have reviewed the integration of JSSP with Industry 4.0. Chaudhry & Khan (2016) [2] performed an extensive review of literature from 1990 to 2014 and highlighted various techniques and approaches used to solve the JSSP problem. A comprehensive review of job shop scheduling models, algorithms used for JSSPs, and the integration of techniques used in Industry 4.0 for solving JSSP were conducted by Zhang et al.

2. Latest Research Trends in SFFJSP

After the first industrial revolution, the concept of industry 1.0 emerged, which is mainly focused on a one-dimensional parameter (i.e., Product Demand). In industry 2.0, the manufacturing facilities focused on product volume and variety. In industry 3.0, the manufacturing facilities shifted from analog to digital controls while considering the three parameters (i.e., product demand, product variety, and product delivery time). Many industries are still undergoing these three revolutions. In Industry 4.0, the technological boom overlapped with all of the conventional approaches to manufacturing and attracted the focus of production managers, researchers, and various governments as well. Scheduling is the pivotal module of production management. Job shop scheduling is one of the most frequently used types of scheduling in manufacturing facilities. In recent years, various research has been conducted to analyze the integration and impacts of the Industry 4.0 environment on job shop scheduling.

2.1. Use of IoT

Leusin et al. [3] embedded MAS into CPS to solve complex dynamic JSSP. IoT is used in that model for extracting real-time data from the shop floor. The fluctuations in work in process (WIP) can be reduced by implementing the approach in the production environment. The conceptual framework proposed is based on a multi-agent system that can be used in numerous stochastic environments for achieving agility and high flexibility in the scheduling of jobs in the production facility.

2.2. Use of Genetic Algorithm

Niehues et al. [4] highlighted the importance of adaptive job shop control under a stochastic environment. The disruptions are included at each stage in the FMS, operated under the JSSP environment. The order shifting by scheduling the timeline is analyzed using a genetic algorithm by the development of a system that is capable of detecting the deviations with the help of location-based data acquisition (DAQ).

2.3. Decision Support System

Grieco et al. [5] presented the application of big data in the production facilities of Bottega Veneta. The job shop scheduling environment is analyzed based on the Decision Support System (DSS). The constraint and mixed-integer linear programming models incorporated with big data technology are used to provide insight for the production managers regarding delivery times and costs. Zhong et al. (2017) [6] did a comprehensive review of studies related to the applications of Intelligent Manufacturing Systems (IMS) on job shop scheduling.

2.4. Decentralization Outperformance

Mehrsai et al. [7] analyzed the JSSP problem under various considerations. It includes a centralized flow environment, FMS with multiple flow possibilities, decentralized sequencing of jobs with a central delivery system, decentralization for real-time data, and decentralization for real-time on-ground and historical data based on multiple agents. Their study concluded that the decentralization offered a substantiating result in JSSP.

2.5. Use of Semi Hierarchal Configuration

Guizzi et al. [8] evaluated the robustness of the JSSP by introducing a semi hierarchal configuration inspired by a cyber-physical system that will result in the combination of proactive and reactive approaches to JSSP. The system sub-divided the actual complex scheduling problem into three small problems. It is then solved at various stages, i.e., several jobs to be produced by the machine with Enterprise Resource Plan (ERP), the sequencing and routing of jobs with the help of CPs, and the identification of jobs at each stage with CPs.

2.6. Use of Heuristic Approaches

Sousa et al. [9] evaluated various heuristic approaches to find the optimal solution for makespan and total weighted tardiness. The Big Data technique is used with the help of various sensors at the facility which provide updated information. The Industry 4.0 environment, along with the conventional approximate method, is used for continuous scheduling of the operations in FMS. The study concluded that the shifting bottleneck algorithm outperformed various algorithms.

2.7. Maximizing Hamiltonian Function

Ivanov et al. [10] solved the multi-stage JSSP problem under FMS. The additional time-dependent processing speeds and machine availability constraints are used for evaluating job lateness and makespan using the optimal control method and maximized Hamiltonian function for a dynamic environment.

2.8. Use of CBJSP

Liu et al. [11] investigated the combined buffer job JSSP problem by formulating the mathematical model and solved using established heuristics techniques. The FJSSP instances are evaluated using the CBJSP. The results of the proposed methodology showed significant performance over the conventional methodology.

2.9. Use of RFID Based IoT

Ding & Jiang [12] provided insight for analyzing the data obtained by RFID-based production control. In their model, IoT facilities were used for extracting the data from the job shop. The three machines JSSP problem is solved using RFID-based IoT enabled smart JSSP. Their model intended to help the production manager to cope with the routine disruptions that occur in the production facility by incorporating smart factory technologies established under Industry 4.0.

2.10. Industry 4.0 in SFFJSP

Ahuett–Garza & Kurfess [13] highlighted the use of various techniques of Industry 4.0 for achieving the smart manufacturing environment. Applications of SFFJSP are analyzed in accordance with various applications to bring insight to the reader.

2.11. Use of Firefly Algorithm

Lunardi et al. [14] implemented the firefly algorithm using the mixed-integer linear programming (MILP) model to extract the smart solutions for FJSSP. Various instances of FJSSP are evaluated using the proposed methodology integrated with fixed and non-fixed availability constraints [15].

2.12. Use of Lagrange Relaxation Method

Yan et al. [16] estimated near-optimal schedules for large-scale JSSPs by developing tightened MILP with constraint & vertex conversion and vertex projection processes with the help of the Lagrange relaxation method. The convergence and complexity were reduced exponentially by the development of the decomposition and coordination method.

2.13. Use of AGVs

Heger & Voß [17] evaluated the mean flow time and mean tardiness of FJSSP based on various priority, routing, and dispatching rules. The multi-purpose autonomous guided vehicles (AGVs) are used in the model to estimate the complex manufacturing system. The study concluded that the use of AGVs in the model along with rules reduces the mean flow time up to 70%.

2.14. Use of HSTL

Dolgui et al. [18] analysed the JSSP by applying the optimal control techniques with the additional hybrid structure terminal logical (HSTL) constraints for optimizing multi-criteria, i.e., cost, delivery time, and makespan. In this model, both control and state variables are defined for a dynamic environment in the supply chain (i.e., multiple suppliers and multiple factories). Process structures are individually highlighted for various customer orders and manufacturing processes. The Flexible Manufacturing System (FMS) is used to execute the operations at multiple workstations.

2.15. Use of DSS with Big Data

Turker et al. [19] offered a framework that comprises of decision support system (DSS) equipped with big data, along with the frequently used dispatching rules such as shortest processing time, early due date, shortest slack time, etc., to increase the performance of job shop under dynamic scheduling. The schedule updates instantaneously based on the criticality of the queue of jobs waiting for the assignment of the workstation. Their study concluded that the contribution of big data fills the gap between theory and practice by considering the real-time dynamic behavior of jobs and machines.

2.16. Development of Standard Dataset

Weber et al. [20] made a major contribution by developing the standardized data set for the JSSP problem. The authors argued that the present data set contains uniformity to some extent and that there is a time of need to create a comprehensive random dataset that can be used not only by operation research (OR) researchers but by production managers. In today’s environment, where Industry 4.0 brings a solution to most of the problems that were not considered while analyzing the JSSP problem, the dataset for comprehensive analysis is needed.

2.17. Use of Q-Learning Algorithm

Zhao et al. [21] proposed a Q-learning algorithm to solve the FJSSP by considering the machine failures. The Q-learning algorithm works on the preemptive strategy and evaluates the consequences of the selected solving approach by the agent. The agent-based approach is used to select the best priority rule that can be used at the instance for selecting the machines and operations when the machine failure occurs.

2.18. Use of RRCF

Liu et al. [22] proposed an operator-based robust right coprime factorization (RRCF) approach to deal with demand fluctuations while maximizing the robustness of the system. The proposed RRCF stabilized the job shop by solving bottlenecks at each stage while considering constant demands and reducing work in process (WIP). To evaluate the effectiveness of (RRCF), the results are compared with the proportional-integral-derivative (PID) controller. Their study concluded that the proposed RRCF outperformed PID and showed low overshoots and more steady-state behavior.

This entry is adapted from the peer-reviewed paper 10.3390/su13147684

References

  1. Geyik, F.; Cedimoglu, I.H. The strategies and parameters of tabu search for job-shop scheduling. J. Intell. Manuf. 2004, 15, 439–448.
  2. Chaudhry, I.A.; Khan, A.A. A research survey: Review of flexible job shop scheduling techniques. Int. Trans. Oper. Res. 2016, 23, 551–591.
  3. Leusin, M.E.; Frazzon, E.M.; Maldonado, M.U.; Kück, M.; Freitag, M. Solving the Job-Shop Scheduling Problem in the Industry 4.0 Era. Technologies 2018, 6, 107.
  4. Niehues, M.; Blum, M.; Teschemacher, U.; Reinhart, G. Adaptive job shop control based on permanent order sequencing. Prod. Eng. 2017, 12, 65–71.
  5. Grieco, A.; Caricato, P.; Gianfreda, D.; Pesce, M.; Rigon, V.; Tregnaghi, L.; Voglino, A. An Industry 4.0 Case Study in Fashion Manufacturing. Procedia Manuf. 2017, 11, 871–877.
  6. Zhong, R.Y.; Xu, X.; Klotz, E.; Newman, S.T. Intelligent Manufacturing in the Context of Industry 4.0: A Review. Engineering 2017, 3, 616–630.
  7. Mehrsai, A.; Figueira, G.; Santos, N.; Amorim, P.; Al-mada-Lobo, B. Decentralized vs. Centralized Sequencing in a Complex Job-Shop Scheduling. In Advances in Production Management Systems. The Path to Intelligent, Collaborative and Sustainable Manufacturing; Springer Science and Business Media LLC: Berlin, Germany, 2017; pp. 467–474.
  8. Guizzi, G.; Vespoli, S.; Santini, S. On The Architecture Scheduling Problem Of Industry 4.0. In Proceedings of the CEUR Workshop; CEUR-WS.org: London, UK, 2017; pp. 94–100.
  9. Sousa, R.A.; Varela, M.L.R.; Alves, C.; Machado, J. Job shop schedules analysis in the context of Industry 4.0. In Proceedings of the 2017 International Conference on Engineering, Technology and Innovation (ICE/ITMC), Madeira, Portugal, 27–29 June 2017; pp. 711–717.
  10. Ivanov, D.; Dolgui, A.; Sokolov, B.; Werner, F.; Ivanova, M. A dynamic model and an algorithm for short-term supply chain scheduling in the smart factory Industry 4.0. Int. J. Prod. Res. 2016, 54, 386–402.
  11. Liu, S.Q.; Kozan, E.; Masoud, M.; Zhang, Y.; Chan, F.T. Job shop scheduling with a combination of four buffering constraints. Int. J. Prod. Res. 2017, 56, 3274–3293.
  12. Ding, K.; Jiang, P. RFID-based production data analysis in an IoT-enabled smart job-shop. IEEE/CAA J. Autom. Sin. 2018, 5, 128–138.
  13. Ahuett-Garza, H.; Kurfess, T. A brief discussion on the trends of habilitating technologies for Industry 4.0 and Smart manufacturing. Manuf. Lett. 2018, 15, 60–63.
  14. Lunardi, W.T.; Cherri, L.H.; Voos, H. A Mathematical Model and a Firefly Algorithm for an Extended Flexible Job Shop Problem with Availability Constraints. In Artificial Intelligence and Soft Computing; Springer International Publishing: Berlin/Heidelberg, Germany, 2018; Volume 1, pp. 235–246. ISBN 9783319912530.
  15. Lukasik, S.; Żak, S. Firefly Algorithm for Continuous Constrained Optimization Tasks. In Proceedings of the International Conference on Computational Collective Intelligence, Wroclaw, Poland, 5–7 October 2009; Springer: Berlin/Heidelberg, Germany, 2009; pp. 97–106.
  16. Yan, B.; Bragin, M.A.; Luh, P.B. Novel Formulation and Resolution of Job-Shop Scheduling Problems. IEEE Robot. Autom. Lett. 2018, 3, 3387–3393.
  17. Heger, J.; Voß, T. Dynamic priority based dispatching of AGVs in flexible job shops. Procedia CIRP 2019, 79, 445–449.
  18. Dolgui, A.; Ivanov, D.; Sethi, S.P.; Sokolov, B. Scheduling in production, supply chain and Industry 4.0 systems by optimal control: Fundamentals, state-of-the-art and applications. Int. J. Prod. Res. 2019, 57, 411–432.
  19. Turker, A.K.; Aktepe, A.; Inal, A.F.; Ersoz, O.O.; Das, G.S.; Birgoren, B. A Decision Support System for Dynamic Job-Shop Scheduling Using Real-Time Data with Simulation. Mathematics 2019, 7, 278.
  20. Weber, E.; Tiefenbacher, A.; Gronau, N. Need for Standardization and Systematization of Test Data for Job-Shop Scheduling. Data 2019, 4, 32.
  21. Zhao, M.; Li, X.; Gao, L.; Wang, L.; Xiao, M. An improved Q-learning based rescheduling method for flexible job-shops with machine failures. In Proceedings of the 2019 IEEE 15th International Conference on Automation Science and Engineering (CASE), Vancouver, BC, Canada, 22–26 August 2019; pp. 331–337.
  22. Liu, P.; Zhang, Q.; Pannek, J. Development of Operator Theory in the Capacity Adjustment of Job Shop Manufacturing Systems. Appl. Sci. 2019, 9, 2249.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
This entry is offline, you can click here to edit this entry!
ScholarVision Creations
Feedback