单机交错排序问题的复杂性证明

The proof of complexity about an interlacing form single-machine scheduling problem

关于共同宽容交货的单机排序问题,对于宽容区间大小给定,位置不固定的情况,给出了5条性质,证明该问题是NP-困难的.

Consided the single machine schedeling problem with a common due window.Corresponding to the following cases that the width of the due window is given and the site of the due window is free,listed five properties about it and proved it is NP-hard.