Optimization methods for tardiness/earliness scheduling problem in job shop environment

Abstract

Motivated by the practical scheduling problem of job shops, this research aims to evaluate unrelated parallel machine scheduling problem with the objective of minimizing tardiness and earliness costs in both deterministic and uncertain job shop environments. In the first section, this study proposes an enhanced model considering effects of maximum allowable tardiness. It compares the total cost provided by the proposed model with the case in which there is no limitation on tardiness. In addition, the existing model in the literature is simplified to reduce computational time and enable corporate scheduling staff to use the model efficiently. The results show the effectiveness of proposed model since it reduces the total cost and computational time in most of the studied scenarios. To account for real-life cases representing uncertainty, in the second step of the research, processing time, setup time, and tooling cost are considered as uncertain input parameters. Robust optimization method is used to deal with uncertainty. The robust counterpart formulation is provided to solve the optimization problem with uncertainty and bring the tradeoff between optimality and robustness. This research considers two performance measures as robust price and hedge value to indicate importance of robust scheduling. Design of experiment (DOE) analysis is used to analyze effect of robust optimization parameters on the cost and computational time. Working experience in job shop environment indicates that there are multiple frequent real-time changes (e.g. processing times, due dates, etc.). In the third step of the research, an automated and adaptive model is proposed to dynamically reschedule the initial schedule based on the real-time data. Considering the rescheduling cost, the model also proposed a rescheduling criteria using project management concept. Scheduling problem is categorized as an NP-hard problem. Therefore, the exact model may not be effective to solve large size problems. Thus, in the last part of this research, we proposed an enhanced Genetic Algorithm (E-GA) based model by optimizing GA operators and proposing hybrid dispatch rule to provide initial solution. The results show the efficiency and effectiveness of proposed model compared to multiple existing methods in the literature Multiple numerical experiments are presented to validate proposed models using data collected from a local job shop that manufacturers aerospace parts. Various performance measurements are evaluated to compare performance of proposed approaches.