论文部分内容阅读
排序问题是一类重要的组合优化问题,它在制造工厂的优化设计、交通枢纽的调度、工程项目进度的控制等方面有着深刻的实际背景和广泛的应用前景。在调度或供应链管理中,目标工期已经变得越来越重要,在许多实际情况中,供应商对产品的供应都是在准时(just in time)规则下完成的,因此交货会出现不同的情形:当供应商提前完工,就会产生提前完工成本;当供应商在工期之后完工,就会产生迟延成本。所以研究合适的工期选择,正是供应商所面对的关键问题。本文在以往工期(duedate)的基础上,讨论了具有窗时(due window)的情况,即一个时间间隔即窗时需要确定,工件在这个区间内完成将不会产生惩罚,工件在规定的窗时前或窗时后完工都会产生提前完工或工期延误成本。窗时具有很强的实际应用背景,在交货时间上给予供应商一定的灵活性,并不是限于特定的交货期(即时间点)。本文分析了相关研究现状,在工件加工时间同时考虑学习和恶化效应存在的模型下,给出公共窗时、松弛窗时、不同窗时三种指派方法,最终证明存在多项式时间算法,使目标函数(提前成本、延误成本、窗时开始时间和窗时规模成本加权和)最小,并给出数值实例说明算法是如何进行的。