Surrogate Based Algorithms for Scheduling with Due Dates

Auburn University, Auburn AL

Investigators

Abstract

This grant provides funding for developing innovative algorithms for solving scheduling problems with due dates. Almost every manufacturing and service enterprise must schedule something; jobs through a shop, customers to appointments, or trucks to delivery stops. Often a specific time for each job, customer etc., called a due date, is promised. Meeting these due dates is very important both for customer satisfaction and economic reasons. It is well known that these are among the most difficult problems to solve optimally. Optimal algorithms, which can solve realistically sized problems, will be developed for basic models, e.g. single processors. These algorithms will combine mathematical programming with traditional scheduling approaches. They will then be extended to more complex models such as flow shops. The algorithms will be computationally tested to verify their efficacy. These tests will also be used to explore what factors make an instance difficult to solve. The results of this research will lead to improved ability to schedule in both manufacturing and service environments. The resulting schedules will have better on-time performance as well as reduced costs. To verify results, one of the algorithms will be incorporated into a larger production control software package being developed for the Tunisian textile industry. Additionally, the solution methods proposed for these problems should also have application to other difficult combinatorial problems, such as routing, network design and analysis, reliability and project selection.