Single-machine Scheduling with Splitable Jobs and Availability Constraints

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


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:



Copyright (c) 2013 REV Journal on Electronics and Communications

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