Scheduling problem is an important combinatorial optimization problem, and it is attracting a lot of attention because of its deep background in the real world and bright future in various application environments. A great feature of the scheduling problem is; there are a lot of models to study, and the algorithms to be applicable to some models are not be able to suit for other problems even if the conditions in the models are changed slightly. The classical scheduling problem usually assumes that all the processing time is constant, while due to many factors ( such as the processing machines, jobs to be processed and processing sequences, etc) the processing time of jobs is not necessarily preserved. In this paper, we consider a new class of scheduling problems-scheduling problems with linear deteriorating jobs in a single-machine scheduling problem with due-window assignment and deteriorating maintenance. The objective is to find jointly the optimal time to perform maintenance, the optimal location and size of the due-window, and the optimal job sequence to minimize the total earliness, tardiness and due-window related costs. We show that the problem has an optimal algorithm and can be optimally solved in O(n2logn) time.%排序问题是一类重要的组合最优化问题,它的深刻的实际背景和广阔的应用前景,引起了广泛的关注.排序问题的一大特点是模型繁多,适用于某一模型的算法,只要将模型的条件稍加变化,该算法就可能不适用.在经典排序问题中,通常假设工件的加工时间是不变的,然而,在许多实际问题中,工件的加工时间受到加工机器设备、工件本身、加工顺序等许多因素的影响而未必是恒定的.文章提出一类新型的排序问题——带有工期窗口和维护时间的线性退化工件的单机排序问题,目标是寻找:1)最优维护的开始时间；2)工期窗口的位置和大小；3)工件的最优排序使得提前完工、误工、工期窗口开始时间和窗口宽度的总费用最小.文章最后给出了这个问题的最优算法,其时间复杂性是O(n2 logn).
展开▼
