带有一个不可用区间的两台平行机可拒绝排序问题（英文）

Order Acceptance and Two Parallel Machines Scheduling Problem with an Availability Constraint

本文主要研究两台平行机排序问题,其中一台机器上有一个固定的不可用区间。此外,生产商可以通过支付惩罚费用来拒绝工件。目标是极小化最大时间表长与惩罚费用之和。本文针对工件可恢复和不可恢复两种情形,分别给出了时间复杂性为O(ns_1P^2)和O(np_(max)s_1P^2)的伪多项式时间动态规划算法.

This paper considers a two parallel machines scheduling problem, which one machine has a fixed availability constraint and the manufacturer can reject orders by paying penalties.The objective is to mini- mize the makespan of the accepted orders plus the total penalties of the rejected orders.Two cases, resumable and nonresumable are discussed in this paper.Moreover, a pseudo-polynomial time algorithm based on dynamicprogramming is proposed for each to solve the problem optimally,which runs in time O（ns_1P^2）and O（np_（max）s_1P^2）,respectively.