A MODEL OF JOB SHOP SCHEDULING TO TACKLE DYNAMIC EVENTS THROUGH SIMULATION DISSERTATION In partial fulfilment of the requirements for the Degree of Doctor of Philosophy from Institut Teknologi Bandung By MUHAMMAD USMAN NISAR Student ID: 33421701 (Doctoral Program in Industrial Engineering and Management) INSTITUT TEKNOLOGI BANDUNG November 2024 i ABSTRACT A MODEL OF JOB SHOP SCHEDULING TO TACKLE DYNAMIC EVENTS THROUGH SIMULATION By Muhammad Usman Nisar Student ID: 33421701 (Doctoral Program in Industrial Engineering and Management) Job shop scheduling (⤷⥀⥀) is an important component of manufacturing systems. Traditional ⤷⥀⥀ models assume static conditions: (1) all the jobs are present at time zero, (2) the attributes of jobs such as release dates (⥙ ⷨ) 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 ⤷⥀⥀ is not static but rather highly dynamic. The ⤷⥀⥀ 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 ⤷⥀⥀. 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 ⤷⥀⥀ instances, struggles computationally to generate optimal solutions for medium-to-large scale ⤷⥀⥀ instances, or on heuristic approaches, which although provide quicker solutions for small-to-large scale ⤷⥀⥀ instances, the solutions obtained are not optimal. Moreover, there is a growing demand for ⤷⥀⥀ 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 ⤷⥀⥀. To tackle these challenges, our research develops a comprehensive series of approaches combining the strengths of exact method, greedy algorithm (⤴ ⷰ⤮), 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 ⤷⥀⥀ instances, so only solutions for small-scale ⤷⥀⥀ instances are used as a benchmark. Next, a greedy algorithm (⤴ ⷰ⤮) is employed: (1) to scale the problem size for small-to-large scale ⤷⥀⥀ instances, and (2) to obtain quick solutions. While ⤴ ⷰ⤮ is computationally efficient, it does not always provide optimal solutions, necessitating the need for a more advanced approach. ii 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.