Polynomial algorithms for single machine scheduling problems with financial constraints. (English) Zbl 0885.90063
Summary: 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.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
largest processing time; single machine scheduling; multiple financial resource constraints; two machine flow shop scheduling; polynomial algorithmsReferences:
| [1] | Carlier, J., Complexité des problèmes d’ordonnancement à constraintes de financement, (Hansen, P.; de Werra, D., Regards sur la Théorie des Graphes (1980), Presses Polytechniques Romandes: Presses Polytechniques Romandes Lausanne), 183-186 |
| [2] | Carlier, J.; Rinnooy Kan, A. H.G., Scheduling subject to nonrenewable-resource constraints, Oper. Res. Lett., 1, 52-55 (1982) · Zbl 0494.90041 |
| [3] | Johnson, S. M., Optimal two and three stage production schedules with setup time included, Naval Res. Logist. Quart., 1, 61-68 (1954) · Zbl 1349.90359 |
| [4] | Slowinski, R., Preemptive scheduling of independence jobs on parallel machine subject to financial constraints, European J. Oper. Res., 15, 366-373 (1984) · Zbl 0535.90045 |
| [5] | Toker, A.; Kondakci, S.; Erkip, N., Scheduling under a non-renewable resource constraint, J. Oper. Res. Soc., 42, 811-814 (1991) · Zbl 0737.90036 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
