Resource loading with time windows

Fabrice Talla Nobibon, Roel Leus, Kameng Nip and Zhenbo Wang

European Journal of Operational Research, 2015, vol. 244, issue 2, 404-416

Abstract: Resource loading appears in many variants in tactical (mid-term) capacity planning in multi-project environments. It develops a rough sketch of the resource usage and timing of the work packages of a portfolio of orders. The orders need to be executed within a time horizon organized into periods, each of which has a known number of workers available. Each order has a time window during which it must be executed, as well as an upper and lower bound on the number of workers that can work on this order in a period. The duration of the order is not fixed beforehand, but depends on the number of workers (intensity) with which it is executed. In this article we define three fundamental variants of resource loading and study six special cases that are common to the three variants. We present algorithms for those cases that can be solved either in polynomial time or in pseudo-polynomial time. The remaining cases are proven to be np-complete in the strong sense, and we discuss the existence of approximation algorithms for some of these cases. Finally, we comment on the validity of our results when orders must be executed without preemption. Although inspired by a number of practical applications, this work focuses on the properties of the underlying generic combinatorial problems. Our findings contribute to a better understanding of these problems and may also serve as a reference work for authors looking to design efficient algorithms for similar problems.

Keywords: Resource loading; Complexity theory; Manpower planning; Preemption (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715000569
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:244:y:2015:i:2:p:404-416

DOI: 10.1016/j.ejor.2015.01.036

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().