Stochastic Online Scheduling with Preemption Penalties

Volume 6, Issue 3, pp 238-250 http://dx.doi.org/10.22436/jmcs.06.03.08

Download PDF

Download XML

• Export citations
  • CITATIONS & REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • ARTICLE CITATION
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)

• 2352 Downloads
• 3601 Views

Authors

Mehdi Heydari - Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran. Mohammad Mahdavi Mazdeh - Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran. Mohammad Bayat - Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran.

Abstract

This paper considers a stochastic online scheduling problem in which a set of independent jobs are to be processed on a single machine. Each job has a processing time, which is a random variable with normal distribution. All the jobs arrive overtime, which means that the existence and the parameters of each job including its processing time specifications and weight are unknown until its release date. Moreover, the actual processing time of each job is unknown until its completion. During the processing, jobs are allowed to be preempted and restarted later. So, the processing time devoted to the job before the preemption is lost and considered as preemption penalty. The objective is to minimize the expected value of the total weighted completion time. Since the problem is strongly NP-hard, a heuristic algorithm is proposed in this paper and is validated using numerical examples. The proposed method utilizes the properties of the normal distribution but it can be used as a heuristic for other distributions, as long as their means and variances are available.

Share and Cite

Keywords

• Stochastic scheduling
• online scheduling
• preemption penalty
• job preemption
• preemption-restart

MSC

•  90B35
•  68M20

References

• [1] C. N. Potts, L. N. V. Wassenhove, , J. Oper. Res. Soc., 43 (1992), 395


• [2] Z. Liu, T. C. E. Cheng, , Information Process. Lett., 82 (2002), 107


• [3] F. Zheng, W. Dai, P. Xiao, Y. Zhao, Competitive strategies for on-line production order disposal problem, In: Proc. of 1st International Conference on Algorithmic Applications in Management, (2005), 46
  • View Article
  • Google Scholar
  • MATH


• [4] F. Zheng, Y. Xu, E. Zhang, , J Comb Optim , 13 (2007), 189


• [5] P. Y. F. Stanley, , Inf Process Lett , 108 (2008), 214


• [6] M. Heydari, S. J. Sadjadi, E. Mohammadi, , Minimizing Int J Adv Manuf Technol, 47 (2009), 227


• [7] D. Chazan, A. G. Konheim, B. Weiss, , Journal of Combinatorial Theory, 5 (1968), 344


• [8] A. G. Konheim, , Probability Theory and Related Fields, 9 (1968), 112


• [9] K. C. Sevcik, , Journal of the ACM, 21 (1974), 65


• [10] G. Weiss, , Advances in Applied Probability, 27 (1995), 827


• [11] T. Kämpke, , Operations Research , 37 (1) (1989), 126


• [12] N. Megow, T. Vredeveld, Approximation results for preemptive stochastic online scheduling, Technical Report 8, Technische Universität , Berlin (2006)
  • Google Scholar


• [13] Manzhan Gu, Xiwen Lu , , Information Processing Letters , Information Processing Letters 109, pp-369(2009)., 109 (2009), 369


• [14] J. Labetoulle, E. L. Lawler, J. K. Lenstra, A. H. G. Rinooy Kan, Preemptive scheduling of uniform machines subject to release dates, In W. R. Pulleyblank, editor, Progress in Combinatorial Optimization, Academic Press, New York, (1984), 245–261
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [15] J. K. Lenstra, A. H. G. Rinooy Kan, P. Brucker, , Annals of Discrete Mathematics, 1 (1977), 243


• [16] N. Megow, Coping with incomplete information in scheduling stochastic and online models, Ph.D. Thesis, Technische Universität Berlin, Published by Cuvillier Verlag Göttingen, Germany (2007)
  • View Article
  • Google Scholar
  • MATH


• [17] Heydari M. Mohammadi, E. Single , machine scheduling with fuzzy preemption penalties, The Journal of Mathematics and Computer Science , 2 (2011), 122