A hybrid local search algorithm for scheduling real-world job shops with batch-wise pending due dates

This paper aims at solving a real-world job shop scheduling problem with two characteristics, i.e., the existence of pending due dates and job batches. Due date quotation is an important decision process for contemporary companies that adopt the MTO (make to order) strategy. Although the assignment of due dates is usually performed separately with production scheduling, there exist strong interactions between the two tasks. Therefore, we integrate these two decisions into one optimization model. Meanwhile, each order placed by the customer defines a batch of jobs, for which the same due date should be set. Thus, the completion times of these jobs should be close to one another in order to reduce waiting time and cost. For this purpose, we propose a dispatching rule to synchronize their manufacturing progresses. A two-stage local search algorithm based on the PMBGA (probabilistic model-building genetic algorithm) and parameter perturbation is proposed to solve the integrated scheduling problem and its superiority is revealed by the applications to a real-world mechanical factory.