Approximation schemes for parallel machine scheduling with non-renewable resources. (English) Zbl 1380.90116
Summary: In this paper, the approximability of parallel machine scheduling problems with resource consuming jobs is studied. In these problems, in addition to a parallel machine environment, there are non-renewable resources, like raw materials, energy, or money, consumed by the jobs. Each resource has an initial stock, and some additional supplies at a-priori known moments in time and in known quantities. The schedules must respect the resource constraints as well. The optimization objective is either the makespan or the maximum lateness. Polynomial time approximation schemes are provided under various assumptions, and it is shown that the makespan minimization problem is APX-complete if the number of machines is part of the input even if there are only two resources.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Artigues, C.; Demassey, S.; Néron, E., Resource-constrained project scheduling: models, algorithms, extensions and applications (2013), John Wiley & Sons |
| [2] | Belkaid, F.; Maliki, F.; Boudahri, F.; Sari, Z., A branch and bound algorithm to minimize makespan on identical parallel machines with consumable resources, Advances in mechanical and electronic engineering, 217-221 (2012), Springer |
| [3] | Briskorn, D.; Choi, B.-C.; Lee, K.; Leung, J.; Pinedo, M., Complexity of single machine scheduling subject to nonnegative inventory constraints, European Journal of Operational Research, 207, 605-619 (2010) · Zbl 1205.90115 |
| [4] | Briskorn, D.; Jaehn, F.; Pesch, E., Exact algorithms for inventory constrained scheduling on a single machine, Journal of Scheduling, 16, 105-115 (2013) · Zbl 1297.90065 |
| [5] | Carlier, J., Problèmes d’ordonnancements à contraintes de ressources: Algorithmes et complexité. Thèse d’état (1984), Université Paris 6 |
| [6] | Carlier, J.; Rinnooy Kan, A. H.G., Scheduling subject to nonrenewable resource constraints, Operational Research Letters, 1, 52-55 (1982) · Zbl 0494.90041 |
| [7] | Carrera, S.; Ramdane-Cherif, W.; Portmann, M.-C., Scheduling supply chain node with fixed component arrivals and two partially flexible deliveries, Proceedings of the 5th international conference on management and control of production and logistics-mcpl 2010, 6 (2010), IFAC Publisher |
| [8] | Gács, P.; Lovász, L., Khachiyan’s algorithm for linear programming, Mathematical Programming Studies, 14, 61-81 (1981) · Zbl 0463.90066 |
| [9] | Gafarov, E. R.; Lazarev, A. A.; Werner, F., Single machine scheduling problems with financial resource constraints: some complexity results and properties, Mathematical Social Sciences, 62, 7-13 (2011) · Zbl 1229.90059 |
| [10] | Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness (1979), San Francisco, LA: Freeman · Zbl 0411.68039 |
| [11] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Kan, A. R., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 |
| [12] | Grigoriev, A.; Holthuijsen, M.; van de Klundert, J., Basic scheduling problems with raw material constraints, Naval Research of Logistics, 52, 527-553 (2005) · Zbl 1122.90349 |
| [13] | Györgyi, P.; Kis, T., Approximation schemes for single machine scheduling with non-renewable resource constraints, Journal of Scheduling, 17, 135-144 (2014) · Zbl 1297.90045 |
| [14] | Györgyi, P.; Kis, T., Reductions between scheduling problems with non-renewable resources and knapsack problems, Theoretical Computer Science, 565, 63-76 (2015) · Zbl 1315.90015 |
| [15] | Györgyi, P.; Kis, T., Approximability of scheduling problems with resource consuming jobs, Annals of Operations Research, 235, 1, 319-336 (2015) · Zbl 1332.90111 |
| [16] | Hall, L. A.; Shmoys, D. B., Approximation schemes for constrained scheduling problems, Proceedings of the 30th annual symposium on foundations of computer science, 134-139 (1989), IEEE |
| [17] | Herr, O.; Goel, A., Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints, European Journal of Operational Research, 248, 123-135 (2016) · Zbl 1346.90351 |
| [18] | Janiak, A.; Janiak, W.; Lichtenstein, M., Resource management in machine scheduling problems: a survey, Decision Making in Manufacturing and Services, 1, 1-2, 59-89 (2007) · Zbl 1231.90199 |
| [19] | Kis, T., Approximability of total weighted completion time with resource consuming jobs, Operations Research Letters, 43, 6, 595-598 (2015) · Zbl 1408.90133 |
| [20] | Laborie, P., Algorithms for propagating resource constraints in ai planning and scheduling: existing approaches and new results, Artificial Intelligence, 143, 151-188 (2003) · Zbl 1079.68622 |
| [21] | Morsy, E.; Pesch, E., Approximation algorithms for inventory constrained scheduling on a single machine, Journal of Scheduling, 18, 6, 645-653 (2015) · Zbl 1333.90051 |
| [22] | Neumann, K.; Schwindt, C., Project scheduling with inventory constraints, Mathematical Methods of Operations Research, 56, 513-533 (2003) · Zbl 1064.90018 |
| [23] | Shabtay, D.; Kaspi, M., Parallel machine scheduling with a convex resource consumption function, European Journal of Operational Research, 173, 1, 92-107 (2006) · Zbl 1125.90023 |
| [24] | Sirdey, R.; Carlier, J.; Kerivin, H.; Nace, D., On a resource-constrained scheduling problem with application to distributed systems reconfiguration, European Journal of Operational Research, 183, 2, 546-563 (2007) · Zbl 1180.90137 |
| [25] | Slowinski, R., Preemptive scheduling of independent jobs on parallel machines subject to financial constraints, European Journal of Operational Research, 15, 366-373 (1984) · Zbl 0535.90045 |
| [26] | Stadtler, H.; Kilger, C., Supply chain management and advanced planning. Concepts, models, software, and case studies (2008), Springer |
| [27] | Toker, A.; Kondakci, S.; Erkip, N., Scheduling under a non-renewable resource constraint, Journal of the Operational Research Society, 42, 811-814 (1991) · Zbl 0737.90036 |
| [28] | Williamson, D. P.; Shmoys, D. B., The design of approximation algorithms (2011), Cambridge university press · Zbl 1219.90004 |
| [29] | Xie, J., Polynomial algorithms for single machine scheduling problems with financial constraints, Operations Research Letters, 21, 1, 39-42 (1997) · Zbl 0885.90063 |
| [30] | Yeh, W.-C.; Chuang, M.-C.; Lee, W.-C., Uniform parallel machine scheduling with resource consumption constraint, Applied Mathematical Modelling, 39, 8, 2131-2138 (2015) · Zbl 1443.90199 |
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.
