具有退化工件和工期窗口安排的排序问题

针对具有退化工件的排序模型,考虑了单机排序和两台机器流水作业的工期窗口安排问题,在这一模型中,工件的加工时间是与其开工时间和退化率有关的一个线性函数。目标是找到一个最优排序和确定工期窗口的开始时间及大小以便最小化所有工件的费用函数,费用函数由四部分组成:提前、延误、工期窗口开始时间和工期窗口大小。对所研究的单机问题,详细地讨论了符合现实情况的几种类型问题,并得到了问题的最优解;对两台机器流水作业问题,给出了多项式算法。

Common Due-window Assignment and Scheduling Problems with Deteriorating Jobs

This paper is devoted to a scheduling problem with simple linear deterioration, that is, the processing time of a job is a simple linear function of its starting time and its deterioration rate. We consider the common due-window assignment problem for the single machine and two machine flow shop. The goal is to schedule the jobs and the due-window so as to minimize the highest cost among all the jobs. The objective function contains four cost components: earliness, tardiness, due-window starting time and size. By analyzing the properties of the optimal schedule, we obtain the due-window starting time and size. For the single machine and two-machine flow shop problems, we present a polynomial time solution respectively. Moreover, some special cases of the single machine are also discussed in detail.