Surrogate Based Algorithms for Scheduling with Due Dates

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

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.