单机排序问题最优解的结构及其求法

The Structure and the Approach to the Optimal Solution to the Problem for Scheduling on a Single Processor

本文研究了单机排序问题|r_i=0|∑|c_i-d_i|最优解的结构．提出了最优解的紧密规则，以及最优解的近似求法．

This paper concerns itself with the scheduling of Jobs or workpieces in the case of penalty for earliness or tardiness around a common due date scheduled on a single processor． We conclude that there is a V-type structure in such kind of problem．Since the recognition version of the problem is NP-complete in ordinary sense,the paper describes optimality conditions only and gives a heuristric algorithm．