Minimization of resource consumption under a given deadline in the two- processor flow-shop scheduling problem (Q1262204)

The paper deals with an extension of the classical two-processor flow- shop problem. Given are the parameter of the process. The scheduler (the algorithm) has a choice as to how much processing time should be assigned to each task. The scheduler can save task processing time by strategic allocation of the resource (e.g. financial outlay, energy, memory, etc.), i.e. the time is inverse proportional to the amount of the resource used. The problem is to find a sequence of tasks and a resource allocation minimizing the total resource consumption under the given deadline common for all tasks. It may be shown that the decision version of this problem is NP-complete, even for the task models with identical derivatives with respect to resource amount on one of the processors and for task processing times independent of the resources on another processor. The reduction may be done either via partition or knapsack. Some efficiently solvable cases of the problem and four (simple and modified) heuristic algorithms are shown. Some generalizations of the proposed approach are also outlined.