Minimization of the makespan in a two-machine problem under given resource constraints

In this paper the classical two-machine flow-shop problem was generalized to the case when job processing times may be reduced linearly by the application of a limited, continuously divisible resource, e.g. financial outlay, energy, fuel, catalyzer etc. It is proved that the decision form of this problem is NP-complete even for the fixed job processing times on one of the machines and identical job reduction rates on another. Some polynomially solvable cases of the problem are identified. Four simple and modified approximate algorithms are presented together with their worst case and experimental analysis. Also, a fast exact algorithm of the branch and bound type based on the shown elimination properties of the problem considered is presented. Some computational results and generalizations (e.g. bicriterial approach) are included as well.