带有交货期窗口和工件可拒绝的单机排序问题

Scheduling a Single Machine with Job Rejection and Due-window Assignment

讨论了带有交货期窗口和工件可拒绝的单机排序问题﹐这一问题是将所有的工件分成两个集合﹐一个是被接受的工件集﹐一个是被拒绝的工件集。假设被接受的每个工件都有一个待定的交货期窗口﹐且所有工件的交货期窗口的大小是相同的﹐如果工件在窗口中完工﹐则不产生任何费用;否则工件提前或延误﹐会产生相应的提前或延误的费用。而对于拒绝工件而言﹐它的费用只与工件有关。这类问题的总费用是2个工件集的费用之和。目标函数是确定被接受工件的最优排序﹐极小化总费用﹐给出了一个动态规划算法﹐并证明了这个问题是多项式时间可解的。

We study a single machine scheduling with job rejection and due-window assignment. The scheduling problem is given by partitioning the jobs into a set of accepted and a set of rejected jobs. We assume that every accepted job has an undetermined due-window and the size of due-window is identical. There is no cost where the job is completed during the due-window, but there is cost where the job is completed prior or after the due-window. The cost of the rejected jobs depends on the rejected jobs. The cost of this problem is the sum cost of two sets jobs. The objective is to determine the optimal sequence of accepted jobs and minimize the total costs. We have provided dynamic programming algorithms, and shown that the problem is solvable in polynomial time.