Abstract
We study the problem of scheduling a set of jobs on a single machine, to minimize the maximum lateness ML or the maximum weighted lateness MWL under stochastic order. The processing time P i , the due date D i , and the weight W i of each job i may all be random variables. We obtain the optimal sequences in the following situations: (i) For ML, the {P i } can be likelihood-ratio ordered, the {D i } can be hazard-rate ordered, and the orders are agreeable; (ii) For MWL, {D i } are exponentially distributed, {P i } and {W i } can be likelihood-ratio ordered and the orders are agreeable with the rates of {D i }; and (iii) For ML, P i and D i are exponentially distributed with rates μ i and ν i , respectively, and the sequence {ν i (ν i +μ i )} has the same order as {ν i (ν i +μ i +A 0)} for some sufficiently large A 0. Some related results are also discussed.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Boxma, O. J., & Forst, F. G. (1986). Minimizing the expected weighted number of tardy jobs in stochastic flow shops. Operations Research Letters, 5, 119–126.
Brown, M., & Solomon, H. (1973). Optimal issuing policies under stochastic field lives. Journal of Applied Probability, 10, 761–768.
Cai, X., & Zhou, X. (2005). Single-machine scheduling with exponential processing times and general stochastic cost functions. Journal of Global Optimization, 31, 317–332.
Chang, C. S., & Yao, D. D. (1993). Rearrangement, majorization and stochastic scheduling. Mathematics of Operations Research, 18, 658–684.
Jackson, J. R. (1955). Scheduling a production line to minimize maximum tardiness. In Management Science research project, UCLA (Research Report 43).
Muller, A., & Stoyan, D. (2002). Comparison methods for stochastic models and risks. New York: Wiley.
Pinedo, M. (2002). Scheduling: theory, algorithms, and systems (2nd ed.). Englewood Cliffs: Prentice Hall.
Sarin, S. C., Erel, E., & Steiner, G. (1991). Sequencing jobs on a single machine with a common due date and stochastic processing times. European Journal of Operational Research, 51, 287–302.
Shaked, M., & Shanthikumar, J. G. (1994). Stochastic orders and their applications. New York: Academic Press.
Shanthikumar, J. G., & Yao, D. D. (1991). Bivariate characterization of some stochastic order relations. Advances in Applied Probability, 23, 642–659.
Zhou, X., & Cai, X. (1997). General stochastic single-machine scheduling with regular cost functions. Mathematical and Computer Modelling, 26, 95–108.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was partially supported by the Research Grants Council of Hong Kong under Earmarked Grants No. PolyU 5146/02E, CUHK 4170/03E, and NSFC Research Funds No. 70329001, 70518002.
Rights and permissions
About this article
Cite this article
Cai, X., Wang, L. & Zhou, X. Single-machine scheduling to stochastically minimize maximum lateness. J Sched 10, 293–301 (2007). https://doi.org/10.1007/s10951-007-0026-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-007-0026-8