Single and Parallel Machine Scheduling with Variable Release Dates

In this paper, we address the identical parallel machine scheduling problem with variable release dates and a common deadline for arrival. This problem occurs in several settings in which the release dates themselves are decision variables with the constraint that all jobs must arrive before or on a common fixed deadline. This deadline can be interpreted as a maximum release date for all jobs. To our knowledge, this problem has not been studied before in spite of many important applications. A first example is a manufacturing facility which uses a Just-In-Time discipline: jobs are released to the shop floor as late as possible to avoid cluttering the system but due to accounting restrictions, mostly related to the MRP (Materials Requirements Planning) logic, all work orders in a time bucket must be released before a fixed deadline. A second example is the receiving area of a warehouse which restricts the arrival of trucks within a time window. The warehouse may schedule its suppliers' trucks so to avoid congestion and provide them with an arrival time, but again, the warehouse's opening hours or external constraints such as circulation bans at certain hours, restrict the arrival of trucks. In these two examples, the deadline constraint cannot be violated, and a central controller must guarantee that all jobs meet such a constraint.