Operations scheduling with multiple resources and transportation considerations

Abstract

We study a scheduling problem with the operations that require renewable as well as non-renewable resources. After an operation has been completed, the non-renewable resource is depleted whereas the renewable resource can be made available for the next operation. Of both the renewable and the non-renewable resources limited amounts are available and they need to be transported to the locations where they are needed. The operations have deadlines, and the availability of the renewable resources depends on the sequence of the operations. Such operations scheduling problems are commonly encountered in the practices of emergency logistics that deliver medical services to the affected areas after a disaster, where renewable resources typically refer to medical teams and non-renewable resources refer to medical supplies. We present a complexity classification for our problem and show where the borderline lies between NP-hardness and polynomial time solvability. We analyse the structural properties of our problem, provide strongly polynomial-time solutions for four special cases and list the cases that are computationally intractable. Finally, we propose a framework of heuristic procedures for solving more general versions of this problem.

Keywords:

• operations scheduling
• renewable resource
• non-renewable resource
• tardiness penalty
• polynomial time algorithms
• complexity analysis