Polynomial algorithms for single machine scheduling problems with financial constraints

This paper deals with the single machine scheduling problem with multiple financial resource constraints. It is shown that the problem can be reduced to the two machine flow shop scheduling problem if the financial resources arrive uniformly over time, and it is also shown that the LPT (Largest Processing Time) rule generates an optimal solution to the problem if the financial resources are consumed uniformly by all the jobs. Hence there exist polynomial algorithms for these two special cases of the problem. (C) 1997 Elsevier Science B.V.