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.
stochastic scheduling common due date quadratic earliness-tardiness penalties V-shape property
Congdian Cheng Chunfu Jia
College of Mathematics and Systems Science Shenyang Normal University Shenyang,110034,Peoples Repub Department of Computer and System Sciences Nankai University Tianjin,300071,Peoples Republic of Chi
国际会议
太原
英文
437-441
2011-02-26（万方平台首次上网日期，不代表论文的发表时间）