Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
针对单机排序问题，提出一种动态规划状态空间松弛方法，通过映射到更小状态空间计算下界，并利用惩罚和状态空间修正技术改进下界，适用于最小化提前与延误总成本的问题。
The problem of sequencing jobs on a single machine to minimize total cost is considered. Machine capacity constraints require that, at any time, at most one job is processed. Also, no machine idle-time between processing jobs is allowed. In contrast to most research, it is not assumed that the cost is a non-decreasing function of completion time. A dynamic programming formulation of the problem is presented. Since the number of states required by this formulation is prohibitively large, the possibilities for branch and bound algorithms are explored. It is shown that the dynamic programming formulation can be relaxed by mapping the state-space onto a smaller state-space and performing the recursion on this smaller state-space, thereby giving a lower bound. Techniques for improving this lower bound through the use of penalties and through the use of state-space modifiers are discussed. Computational results are presented for the problem in which each job has a due date, and the objective is to minimize the sum of holding costs for jobs completed before their due date and tardiness costs for jobs completed after their due date.