Single-machine Scheduling with Splitable Jobs and Availability Constraints

Abstract

This paper deals with a single machine scheduling problem with availability constraints. The jobs are splitableand lower bound on the size of each sub-job is imposed. The objective is to find a feasible schedule that minimizesthe makespan. The proposed scheduling problem is proved to be NP-hard in the strong sense. Some effective heuristicalgorithms are then proposed. Additionally, computational results show that the proposed heuristic performs well.