SCHEDULING INDEPENDENT TASKS WITH MULTIPLE-MODES

In this paper a nonpreemptive scheduling problem is studied in which a set of independent tasks must be processed on a set of discrete and renewable resources. Each resource can be used at any time by a single task at most. Each task can be carried out in several given alternative modes, that is, by using different resource sets and with different processing times. The objective of the problem is to determine a mode and a starting time for each task in such a way that the makespan is minimized. The problem instances are represented by means of a graph model. The complexity of the problem is studied and several particular cases are identified which remain NP-hard. Upper and lower bounds on the optimal value of the objective function are identified which correspond to some dimensional parameters of the graph. A heuristic iterative solution procedure is sketched and a numerical example is presented.