论文部分内容阅读
生产和生活中,调度有着广泛的应用。例如在灾害救援中,救援物资和人员的调度;在交通运输业中,公交车、火车的安排,快递员的派货;在生产制造业中,工厂车间里的机器安排、工件的加工顺序;在服务业中,如学校教师的排课安排等等,这些都是生活中遇到的调度问题。这些例子说明生产和生活中,调度问题到处可见。这也是为什么越来越多的研究人员和学者参与到调度理论的研究中。调度是一类组合最优化问题。它是研究如何把任务分配给稀缺资源使其在一定时间内最优的完成任务。许多的文献是以工厂车间里机器上的加工安排为模型进行研究的。本文研究了一个带有周期性维护的单机调度问题。在这个问题中,只有一台需要周期维护的机器,维护间隔固定不变,维护时长随当前维护间隔内工件加工总量线性递增。工件所有的信息都是已知的,工件不可中断。目标函数是最小化时间表长即使最后一个工件的完工时间最小。本文所做的主要工作如下:1.证明了FFD-LS2I算法的最坏情况界。首先给出了一个例子说明FFD-LS算法的最坏情况界可能是任意大的数。接着对FFD-LS算法的最坏情况界做了详细的分析,然后对FFD-LS算法做了改进得到FFD-LS2I算法并证明了FFD-LS2I算法最坏情况界。2.证明了不可逼近性。证明了FFD-LS2I算法最坏情况界之后,作者猜测这个算法可能是一个最好的多项式时间算法。然后就证明所研究的调度问题不存在比最坏情况界2更小的多项式时间算法除非P=NP。从而证明了从最坏情况界上,FFD-LS算法和FFD-LS2I算法分别是各自情况下的最好的多项式时间算法。接着回答了一篇文献里的一个开放性问题。3.通过数值实验验证了FFD-LS2I算法最坏情况界,并且找出了FFD-LS2I算法最大误差以及平均误差与工件个数、大小等变量的关系。