V-shape Property for the Quadratic JIT Schedules with Random Processing Times

摘要

This article addresses the problem of scheduling n jobs with random processing times on a machine so as to minimize the expected sum of squared deviations (ESSD) of job completion times from a common due date.We mainly concern the V-shape property of optimal solutions.Through a large and deep stochastic analysis,we obtain the following results and conclusions.A sufficient condition for an optimal sequence to be V-shaped is proposed and proved.The well known equivalence relation between the deterministic unconstrained sum of squared deviations (SSD) problem and the deterministic completion times variance (S-CTV) problem is extended to the situation with the processing times to be independent random variables.In addition,we also show the optimal solution of ESSD problem may not possess V-shape property by a counterexample.