On Rescheduling for Two-Machine Flow Shop System with the Arrival of New Jobs

摘要

In this paper, we consider the rescheduling problem for a two-machine flow shop system with the arrival of new jobs, in which a set of original jobs has been given a planned schedule (but has not been executed) on a two-machine flow shop system to minimize the makespan, when a set of new jobs arrives. The production planner needs to insert the new jobs into the planned schedule without excessively disrupting it to minimize the makesapn on the original and the new jobs. The disruption is measured by the maximum time deviation for any given original job, between the original and new schedules. We examine two special models and a general model. In the first special model, the maximum time deviation appears as a constraint. In the second special model, the maximum time deviation appears as the part of the cost objective. In the general model, the maximum time deviation appears both as a constraint and as the part of the cost objective. For the two special models, we prove that they are NP-hard and accordingly the general model is also NP-hard. Furthermore we propose three heuristic algorithms to solve the general model followed by a numerical example.