Exact approaches for the single machine scheduling problem with distinct time windows

Session : GTSS1 / GTSS1 : Exact methods for scheduling problems
Bruno Rosa, Philippe Michelon et Zacharie Ales

The emergence of the Just in Time management system highlighted the importance of carefully planning production activities. Reducing earliness and tardiness in job scheduling may provide a significant cost reduction. Completing a job with tardiness, i.e., after the desired completion date) may result in contractual penalties, loss of credibility of the company and reduced sales. Similarly, completing a job before the desired date may lead to extra financial costs due to the need for early capital availability, storage space or other resources to maintain and manage the inventory. In many situations, the jobs must be completed in distinct time windows rather than before given due dates. Uncertainties and tolerances related to the jobs characteristics lead to time windows of various size. The Single Machine Scheduling Problem with Distinct Time Windows (SMSPTW) discussed in the present paper consists in determining the time in which the jobs must be performed to minimize the weighted sum of earliness and tardiness penalties of the jobs. This is a NP-hard problem with many practical applications in manufacturing industries, chemical processes and PERT/CPM schedules, among others [1]. The difficulty of the SMSPTW and its numerous applications have motivated the development of many efficient resolution algorithms [1]. However, to our knowledge, no exact method has currently been proposed to tackle this problem. We present a Mathematical Programming model and a Constraint Programming model for the SMSPTW. The efficiency of the models are compared over a set of instances.

Mots clés : job scheduling, mathematical programming, constraint programming