A common due-date assignment problem with job rejection on parallel uniform machines
研究两台平行同速机上公共工期分配问题，允许拒绝部分作业，目标是最小化提前延误成本、工期成本和拒绝成本之和，并证明可在多项式时间内求得最优解。
We study a common due-date assignment problem on two parallel uniform machines. The jobs are assumed to have identical processing times, and job-dependent and asymmetric earliness and tardiness unit costs. The scheduler may process only a subset of the jobs, i.e. the option of job-rejection is allowed. The objective function consists of three cost components: the total earliness-tardiness cost of all scheduled jobs, the cost of the common due-date, and total rejection cost. For a given number of rejected jobs and a given due-date, the problem is reduced to a non-standard linear assignment problem. Consequently, the optimal solution is shown to be obtained in polynomial time in the number of jobs. The case of a given (possibly restrictive) due-date, the extension to a setting of more than two machines, and a number of special cases, are also discussed.