New Challenges on Scheduling Theory

Co-authorMarton Drotos

We address a resource levelling problem in a parallel machine environment. Given a set of m parallel machines, one renewable resource, and a set of n tasks each dedicated to exactly one of the parallel machines. Each task has a processing time, an earliest start time, a deadline, and a resource requirement. The resource has a capacity, but it can be used above this capacity which is the overtime usage of the resource. A schedule with minimum overtime resource usage is sought. We provide several complexity results and propose a heuristic algorithm which reduces the problem to single machine ones, where each single machine problem is equivalent to a TSP with time windows and start time dependent costs.