Stochastic Online Scheduling with Preemption Penalties


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

  • Share on Facebook
  • Share on Twitter
  • Share on LinkedIn
ISRP Style

Mehdi Heydari, Mohammad Mahdavi Mazdeh, Mohammad Bayat, Stochastic Online Scheduling with Preemption Penalties, Journal of Mathematics and Computer Science, 6 (2013), no. 3, 238-250

AMA Style

Heydari Mehdi, Mazdeh Mohammad Mahdavi, Bayat Mohammad, Stochastic Online Scheduling with Preemption Penalties. J Math Comput SCI-JM. (2013); 6(3):238-250

Chicago/Turabian Style

Heydari, Mehdi, Mazdeh, Mohammad Mahdavi, Bayat, Mohammad. "Stochastic Online Scheduling with Preemption Penalties." Journal of Mathematics and Computer Science, 6, no. 3 (2013): 238-250


Keywords


MSC


References