A MODEL OF JOB SHOP SCHEDULING TO TACKLE DYNAMIC EVENTS THROUGH SIMULATION

• Main Author: Usman Nisar, Muhammad
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/86689
• Institution: Institut Teknologi Bandung

Job shop scheduling (JSS) is an important component of manufacturing systems. Traditional JSS models assume static conditions: (1) all the jobs are present at time zero, (2) the attributes of jobs such as release dates (rj ) are known, (3) machines remain always available without breaking down or need for maintenance, (4) no new job arrives during production, and so on. However, these conditions are very restrictive in practical manufacturing scenario. In practical, the JSS is not static but rather highly dynamic. The JSS experiences numerous dynamic events which change the initial state of the system, induce system nervousness, reduce manufacturing efficiency, and in extreme cases, make the schedule infeasible. Upon the occurrence of such dynamic events, rescheduling gains theoretical and practical importance, adding to the further complexity to the JSS. Numerous studies are dedicated to address these challenges with various solution approaches. These solution approaches typically focus on exact method, which although provides optimal solutions for small scale JSS instances, struggles computationally to generate optimal solutions for medium-to-large scale JSS instances, or on heuristic approaches, which although provide quicker solutions for small-to-large scale JSS instances, the solutions obtained are not optimal. Moreover, there is a growing demand for JSS system that not only manage the scheduling process under dynamic events but also provide monitoring, control, and prediction capabilities to address these dynamic aspects of JSS. To tackle these challenges, our research develops a comprehensive series of approaches combining the strengths of exact method, greedy algorithm (GrA), and Greedy Randomized Adaptive Search Procedure (GRASP) algorithm. We start with the exact method to benchmark the solutions for comparing it with the other approximate methods. Since the computational limitation of exact method does not allow us to get the optimal solutions for medium-to-large scale JSS instances, so only solutions for small-scale JSS instances are used as a benchmark. Next, a greedy algorithm (GrA) is employed: (1) to scale the problem size for small-to-large scale JSS instances, and (2) to obtain quick solutions. While GrA is computationally efficient, it does not always provide optimal solutions, necessitating the need for a more advanced approach. The core of our solution approach is a novel GRASP algorithm. This algorithm is designed to balance the quality of the solution with computational effectiveness. Our GRASP approach incorporates two strategies: intensification and diversification. In the intensification strategy: (1) the algorithm systematically analyzes the tardiness of each job, (2) compute the tardiness contribution of each operation to the total tardiness, (3) list operations based on their tardiness contribution value, and (4) apply a directed swapping procedure based on the tardiness contribution value. For the directed swapping procedure, the operation with the significant tardiness contribution value swaps the operation with its predecessor, successor, and other operations on the same machine such that the precedence relationship and dependency relationship among operations are still respected. If no further improvements using the intensification strategy can be made, we employ the diversification strategy. Our diversification strategy incorporates two techniques: (1) random swapping, and (2) random restarting. Through novel GRASP, the quality of the solution improves significantly while maintaining computational efficiency. For example, the percentage gap of 13.82% for GrA and the exact method is reduced to just 3.43% using the GRASP algorithm. Additionally, GRASP’s computational time is significantly lower than exact methods, while being comparable to GrA. In addressing dynamic events, our study categorized them into three types based on the impact they make on scheduling process: (1) low impact (LiDE), (2) medium impact (MiDE), and (3) serious impact (SiDE). Our dissertation focuses on SiDE as they significantly impact the scheduling processing by inducing system nervousness and minimizing the manufacturing efficiency. These events include new jobs arrival (NJA), rush orders (RO), machine failure (MF), and scheduled machine maintenance (SMM). A comprehensive rescheduling procedure is developed to tackle SiDE. A proactive- reactive (Pact ? Ract) rescheduling strategy is used to minimize the impact of SiDE regularly through Pact and on immediate basis through Ract . To define the rescheduling trigger, a hybrid (periodic and event-driven) (Hyb.) rescheduling policy is used, which triggers periodic (pe ) rescheduling for (Pact) to tackle NJA and SMM, and event-driven (ED) rescheduling for Ract rescheduling to minimize the impact of MF and RO. To rescheduling jobs upon the rescheduling triggers, a right-shift (RF) rescheduling method is used for MF and a regeneration (Reg) rescheduling method is used for NJA, RO, and SMM. This rescheduling procedure is adaptable, minimizing the total tardiness of jobs. Our results demonstrate that the Ract rescheduling strategy performs better in minimizing tardiness than Pact rescheduling strategy. To further enhance system’s ability to handle SiDE and provide monitoring, control, and prediction capabilities, we integrate simulation models based on the concept of Digital Twin (DT) technology. A DT is a virtual replica of the physical production system, enabling us to simulate different scenarios and predict the outcomes of various scheduling strategies. Two types of simulation models are developed in this context: (1) simulation models considering priority rules (FIFO, LIFO, SPT, SRPT, EDD, and CR), and (2) simulation models considering SiDE. iii Through these simulation models, we assess the performance of JSS under different varying conditions. Most importantly, our simulation models considering SiDE demonstrate that the combination of Pact and Ract rescheduling strategies effectively manages SiDE , providing a feasible solution for JSS in dynamic environments, while providing the monitoring, control, and prediction capabilities. In conclusion, our research addresses key gaps in JSS by developing a comprehensive series of solution approaches that integrate exact method, GrA, GRASP and simulation techniques. Our novel GRASP offers an effective balance between solution quality and computational efficiency, while our rescheduling procedures and DT simulations provide practical tools for managing practical manufacturing disruptions. This approach not only advance the theoretical understanding of JSS but also offer practical solutions.