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

Abstract:

This article addresses the problem of scheduling 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 time 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.

• Periodical: Advanced Materials Research (Volume 505)
• Pages: 82-89
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.505.82
• Online since: April 2012
• Authors: Cong Dian Cheng, Chun Fu Jia
• Keywords: Common Due Date, Quadratic Earliness-Tardiness Penalties, Stochastic Scheduling, V-Shape Property

References

[1] K. R. Baker and G. D. Scudder: Oper Res. Vol. 38 (1990), p.22

[2] A. G. Merten and M. E. Muller: Mgmt. Sci. Vol. 18 (1972), p.518

[3] S. Eilon and I. C. Chowdhury: Mgmt. Sci. Vol. 23 (1997), p.567

[4] V. Vani and M. Raghavachair: Oper Res. Vol. 35 (1987) , p.111

[5] U. Bagchi, R. S. Sullivan and Y. L. Chang: Mgmt. Sci. Vol. 33 (1987), p.894

[6] U. Bagchi, Y. L. Chang and R. S. Sullivan: Naval Res Logist Vol. 34 (1987), p.739

[7] P. De, J. B. Ghosh and C. E. Wells: Management Science Vol. 35 (1989), p.1143

[8] P. De, J. B. Ghosh and C. E. Wells: Computers Opns Res. Vol. 17 (1990), p.231

[9] X. Cai: European Journal of Operational Research Vol. 91 (1996), p.118

[10] V. R. Prasad and D. K. Manna: Naval Res Logist Vol. 44 (1997), p.97

[11] C. Jia, in: Proceedings of the 4th world congress on intelligent control and automation, Shanghai, 2002, pp.786-796

[12] C. Jia: OR Transaction Vol. 18 （2004）, p.1

[13] J. Mittenthal and M. Raghavachair: Oper Res.Vol. 41 (1993), p.786

[14] X. Cai and F.S. Tu: Naval Res Logist Vol. 43 (1996), p.1127

[15] A. Federgruen and G. Mosheiov: Oper Res. Vol.45 (1997), p.66

[16] X.D. Qi, G.Yin and J.R. Birge: Stochastic Anal Appl，Vol.18 (2000)， p.635

[17] H.Y. Tang, C.L. Zhao and C.D. Cheng: Sci China SerA-Math Vol. 51 (2008), p.273

[18] U.M. Al-Turki, J. Mittenthal and M. Raghavachari: Naval Res Logist Vol.43 (1996), p.573.

[19] C.D. Cheng, H.Y. Tang and C.L. Chao: Sci China Ser A-Math Vol.51 (2008), p.864

[20] C. Jia: Operation Research Letter Vol. 28 (2001), p.199

[21] S.M. Ross: Stochastic Processes (Wiley,1983).