Surrogate Based Algorithms for Scheduling with Due Dates

这项拨款为开发创新算法提供资金，用于解决有到期日的调度问题。几乎每个制造和服务企业都必须安排一些事情；通过商店的工作，顾客的预约，或卡车的送货站。通常每个工作、客户等都有一个特定的时间，称为截止日期。无论是出于客户满意度还是经济原因，按时完成这些任务都是非常重要的。众所周知，这些都是最难最优解决的问题。最优算法，可以解决实际规模的问题，将开发基本模型，如单处理器。这些算法将数学规划与传统调度方法相结合。然后将它们扩展到更复杂的模型，如流程商店。这些算法将进行计算测试以验证其有效性。这些测试还将用于探索使实例难以解决的因素。本研究的结果将有助于提高在制造和服务环境中的调度能力。由此产生的时间表将具有更好的准时性能以及降低成本。为了验证结果，其中一种算法将被纳入正在为突尼斯纺织业开发的一个更大的生产控制软件包中。此外，针对这些问题提出的解决方法也应适用于其他复杂的组合问题，如路由、网络设计与分析、可靠性和方案选择。

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.