一个有宽容交货期的单机加权超前工件数问题

数学与计算科学学院数学与应用数学专业 李冰山

（学号：2003041045）

指导教师：顾燕红

摘 要:本文研究一个存在共同宽容交货期(Common Due Window (CDW))的单机排序问题。目标是最小化加权超前总工件数。文中考虑这个问题的两种情况：CDW是非限制性的及CDW是限制性的。首先通过对单机问题的这两种情况的最优解性质分析而证得其是等价的，再设计求解此两种情况的伪多项式动态规划算法及多项式近似算法；然后讨论一种常见的特例的多项式算法。最后对双平行机问题的这两种情况进行初步的探讨分析，同时给出非限制性情况的伪多项式动态规划算法。

关键 词：排序；宽容交货期；超前完工工件；动态规划算法；近似算法

Abstract: This paper addresses a single-machine scheduling problem with a common due window for each job. The objective is to minimize the total weighted number of early jobs. Two scenarios are investigated in this paper. In one scenario the common due window is unrestricted, and it is restricted in the other. Some properties on the optimal solutions of these scenarios are proposed to prove that these two scenarios are equivalent for the objective of our problem. Successively a pseudo-polynomial dynamical programming algorithm and a polynomial approximate algorithm are designed to solve our problem. Then a polynomial algorithm for a reasonable special case is presented. Finally, a preliminary discussion is given on the two scenarios of the two parallel-machines problem and the pseudo-dynamic programming algorithm is designed for the scenario that the common due window is unrestricted.

Key words：Scheduling; Due window; Early job; Dynamical programming algorithm; Approximate algorithm

教师点评：李冰山同学通过对前期收集的文献进行研究整理，对国内外研究状况非常了解。研究方法思路清晰，设计科学。对所研究问题阐述明确，论证严密，结论可信。

文章的组织合理，写作规范，反映出李冰山同学具有一定的数学基础。对相关算法进行改进，具有一定的创新性。本人认为这是一篇优秀的本科毕业论文。