Single machine scheduling problems with generalised due-dates and job-rejection
研究了单机调度问题，其中作业的到期日由其在序列中的位置决定，且允许拒绝部分作业并支付惩罚成本。针对最大拖期加拒绝成本、总拖期加拒绝成本两个目标，证明了NP难性，并提出了伪多项式动态规划和高效启发式算法。
We study single machine scheduling problems. Generalised due dates are assumed, i.e. job due dates are specified according to the positions of the jobs in the sequence, rather than their identity. Thus, assuming that due dates are numbered in a non-decreasing order, the jth due date refers to the job assigned to the jth position. In addition, we allow the option of job rejection, i.e. not all jobs must be processed. In this case, the scheduler is penalised for each rejected job, and the total rejection cost becomes part of the objective function. Two objective functions are considered: maximum tardiness plus rejection cost, and total tardiness plus rejection cost. Both problems are proved to be NP-hard. Pseudo-polynomial dynamic programmes and efficient heuristics are introduced and tested numerically.