单机带有不可用区间的松弛工期的排序问题

研究了在单机情形下具有不可用区间的松弛工期问题，不可用区间意味着在此区间不允许工件加工，且工件中断可恢复。松弛工期是工件加工时间加上1个给定的常数，这个常数为决策变量，排序的任务是给所有工件分配工期，同时确定工件的加工次序以使得目标函数值最小。目标函数值包括由于工件误工、提前及工期分配而导致的相关损失。根据不同的损失系数关系讨论了松弛工期的范围，提出动态规划算法。证明了动态规划的时间复杂性为O((P+T－pmin)nP2)。通过算例分析说明了算法的可行性。

Single-Machine Scheduling Problem with Unavailability Period for Slack Due Date

The single-machine problem with unavailability period for slack due date is studied. Unavailability period means that the processing job is not allowed in this period. Slack due date means that the due date is equal to its processing time plus a constant, where the constant is the decision variable. The aim is to assign the slack due and minimize the objective function. The objective function includes the early work, late work and slack due date. It discusses the range of slack due date by cost coefficients, and designs a dynamic programming algorithm to solve this problem. It is prove that the optimal solution can be obtained in O((P+T－Pmin)nP2) time. Finally, a numerical example is presented to illustrate the feasibility of the algorithms.