Single-machine Scheduling with Splitable Jobs and Availability Constraints

  • Van Huy Nguyen Faculty of Computer Science & Engineering, Ho Chi Minh city University of Technology
  • Nguyen Huynh Tuong Faculty of Computer Science & Engineering, Ho Chi Minh city University of Technology
  • Hua Phung Nguyen Faculty of Computer Science & Engineering, Ho Chi Minh city University of Technology
  • Thanh Hien Nguyen Faculty of Information Technology, Ton Duc Thang University
DOI: https://doi.org/10.21553/rev-jec.51

Abstract

This paper deals with a single machine scheduling problem with availability constraints. The jobs are splitable and lower bound on the size of each sub-job is imposed. The objective is to find a feasible schedule that minimizes the makespan. The proposed scheduling problem is proved to be NP-hard in the strong sense. Some effective heuristic algorithms are then proposed. Additionally, computational results show that the proposed heuristic performs well.
Published
2013-10-01
Issue
Vol. 3, No. 1-2 (Jan-Jun, 2013)
Section
Regular articles
An author's submission implies that the manuscript has not been published previously, and is not currently submitted for publication elsewhere. Submission also implies that the Corresponding Author has consent of all authors (the Authors). Upon acceptance for publication transfer of copyright will be made to the Publisher of REV-JEC, who guarantees that full content of the published article is freely distributed on the Journal's website. The copyright transfer gives the Publisher of REV-JEC full authority to resolve any complaints of misuse or abuse (such as infringement or plagiarism) of the published article. The Authors have the freedom to redistribute and reuse the published article in any medium or format for any purpose, provided the original published article is properly cited. An article submission implies author agreement with this policy.