Single machine scheduling problem with a common deadline and resource dependent release dates. (English) Zbl 0743.90066
We have \(n\) independent jobs which can be performed in a single machine so that each job runs in a non-interruptable time interval of length \(b_ i\), which is disjoint from the same interval of other jobs. Each job has a different availability time \(t_ i\) at the start. The jobs demand \(r_ i\) amounts of resource, and the \(i\)-th job must satisfy the following condition: \(t_ i=b_ i-a_ ir_ i\). The paper deals with the problem of minimizing the sum of used resources in a limited total schedule time. NP-completeness is proved in general, but approximate algorithms are given for some special cases. Some numerical examples were also tested.
Reviewer: A.P.Bosznay (Budapest)
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | Du, J.; Leung, J. Y.-T., Minimizing total tardiness on one machine is NP-hard, Mathematics of Operations Research (1990), to appear · Zbl 0714.90052 |
| [2] | Grabowski, J.; Janiak, A., Job-shop scheduling with resource time models of operations, European Journal of Operational Research, 28, 58-63 (1987) · Zbl 0614.90048 |
| [3] | Jackson, J. R., Scheduling a production line to minimize maximum tardiness, (Research Report (1955), The University of California at Los Angeles) |
| [4] | Janiak, A., Time-optimal control in a single machine problem with resource constraints, Automatica, 22, 6, 745-747 (1986) · Zbl 0608.90044 |
| [5] | Janiak, A., General flow-shop scheduling with resource constraints, International Journal of Production Research, 26, 6, 1089-1103 (1988) · Zbl 0639.90050 |
| [6] | Janiak, A., Control of the processes between converter plants and a blooming mill in steel mills, (Technical Report of the Institute of Engineering Cybernetics (1988), Technical University of Wrocław), No. 73/88 |
| [7] | Janiak, A., One-machine scheduling with allocation of continuously-divisible resource and with no precedence constraints, Kybernetika, 23, 4, 289-293 (1987) · Zbl 0635.90048 |
| [8] | (Kowalowski, H., Automatyzacja dyskretnych procesów przemysłowych (1984), WNT) |
| [9] | Lenstra, J. K.; Rinnooy Kan, A. H.G.; Brucker, P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343-362 (1977) · Zbl 0301.90025 |
| [10] | Nowicki, E., Minimalizacja Kosztu w jednomaszynowym problemie szeregowania ze zmiennymi czasami gotowości zadań, (Proceedings of a conference: “Problematyka budowy i eksploatacji maszyn w ujȩciu systemowym”. Proceedings of a conference: “Problematyka budowy i eksploatacji maszyn w ujȩciu systemowym”, Kraków (1986)), 70-75 |
| [11] | (Williams, T. J., Analysis and Design of Hierarchical Control systems: With Special Reference of Steel Plant Operations (1986), North-Holland: North-Holland Amsterdam) |
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.
