The single machine stochastic scheduling with the weighted job tardiness minimization

Abstract

This paper considers scheduling n jobs on a single machine where the job processing times and due dates are independent random variables with arbitrary distribution functions. We consider the case that the weighted job tardiness in expectation is minimized. It is assumed that job’s due dates are compatible with processing times and weights. We show that the jobs should be sequenced in decreasing stochastic order of their due dates.

Keywords

Stochastic scheduling / stochastic order / tardiness

References

[1] Chang C.-S., Yao D.D.. Rearrangement, majorization and stochastic scheduling. Mathematics of Operation Research, 1993, 18: 658-684.

[2] Jia C.. Minimization in stochastic flow shop. Operation Reearch Letters, 1998, 23: 109-111.

[3] Forst F.G.. Stochastic sequencing on one machine with earliness and tardiness prnalties. Probability in the Engineering and Informational Sciences, 1993, 7: 291-300.

[4] Li W., Glazebrook K.D.. On stochastic machine scheduling with general distributional assumptions. European Journal of Operational Research, 1999, 105: 525-536.

[5] Pinedo M.. Scheduling: Theory, Algorithms, and Systems, 1995, Englewood Cliffs, NJ: Pretice-Hall.

[6] Pinedo M.. Stochastic scheduling with release dates. Operations Research, 1983, 31: 559-572.

[7] Shaked M., Shanthikumar J.G.. Stochastic Orders and Their Applications, 1994, San Diego: Academic Press.