Online Scheduling in Minimizing Makespan on Identical Parallel Processor with Release Date

Authors

  • Syarifah Zyurina Nordin
  • Lou Caccetta

DOI:

https://doi.org/10.11113/matematika.v30.n0.740

Abstract

In this paper, we address a non-preemptive task scheduling problem with an objective function of minimizing the makespan. We consider online scheduling with release date on identical parallel processing system with centralized and no splitting structure. Multi-steps heuristic algorithms are proposed to solve this non-deterministic scheduling problem. A computational experiment is conducted to examine the effectiveness of the proposed multi-steps method in different size problem. The computational results show that all the proposed heuristics obtain good results with the gap between optimal solutions are less than 10% even for a large date set. The experiment is performed using Microsoft Visual C++ programming software in windows environment.

Keywords: Online scheduling; Minimizing makespan; Identical parallel processor; Release date.

2010 Mathematics Subject Classification: 68M20, 90B36, 90C27.

Downloads

Published

01-12-2014

How to Cite

Nordin, S. Z., & Caccetta, L. (2014). Online Scheduling in Minimizing Makespan on Identical Parallel Processor with Release Date. MATEMATIKA, 30, 71–84. https://doi.org/10.11113/matematika.v30.n0.740

Issue

Volume 30 (December 2014) - Special Issue

Section

Mathematics

License

Copyright of articles that appear in MATEMATIKA: MJIAM belongs exclusively to Penerbit UTM Press, Universiti Teknologi Malaysia. This copyright covers the rights to reproduce the article, including reprints, electronic reproductions or any other reproductions of similar nature.