Single machine scheduling with randomly compressible processing times

This work is concerned with single machine scheduling with random compression of processing times. The objective is to find the optimal sequence to minimize the cost based on earliness, tardiness and compression. The analysis is carried out under a common due date, Both absolute derivation cost and squared derivation cost are considered. For both constrained problems and unconstrained problems, it is shown that an optimal schedule must be V-shaped. Remarks on common slack model is also provided.