Single-machine Scheduling with Splitable Jobs and Availability Constraints

Van Huy Nguyen, Nguyen Huynh Tuong, Hua Phung Nguyen, Thanh Hien Nguyen

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.


Full Text:

PDF


DOI: http://dx.doi.org/10.21553/rev-jec.51

Copyright (c) 2013 REV Journal on Electronics and Communications


Copyright © 2011-2020
Radio and Electronics Association of Vietnam
All rights reserved