A Lazy-Constraints Approach to Resource-Constrained Project Scheduling

Lerch, Dennis; Trautmann, Norbert (16 December 2019). A Lazy-Constraints Approach to Resource-Constrained Project Scheduling. In: IEEEInternational Conference on Industrial Engineering and Engineering Management (IEEM). Macau. 15.-18.12.2019.

[img] Text
A Lazy-Constraints Approach to Resource-Constrained Project Scheduling.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (185kB) | Request a copy

We study the complex combinatorial optimization problem to schedule the activities of a single project with the objective to complete the project within the shortestpossible
amount of time such that the limited resource capacities as well as the prescribed precedence relations between pairs of the activities are taken into account. In addition
to various specific solution algorithms, the related literature proposes several Mixed-Integer Linear Programming (MILP) models, but these models remain complex to solve even for small-sized instances. We present a novel approach based on an MILP model in which the resource-capacity constraints are formulated for all inclusion-minimal sets of activities which, due to the limited capacities of the resources, cannot be processed
simultaneously.We propose to remove these constraints from the model and iteratively add those constraints back which are violated in the solutions obtained. For a set of
test instances from the literature, our computational results indicate that with respect to both, the deviation of the project duration obtained from the lower bound devised from the critical-path length and the number of instances solved to optimality, the novel lazy-constraints approach outperforms ten state-of-the-art MILP models.

Item Type:

Conference or Workshop Item (Paper)

Division/Institute:

03 Faculty of Business, Economics and Social Sciences > Department of Business Management > Institute of Financial Management > Professorship for Quantitative Methods in Business Administration

UniBE Contributor:

Lerch, Dennis Julian and Trautmann, Norbert

Subjects:

600 Technology > 650 Management & public relations

Series:

Proceedings of the 2019 IEEE International Conference on Industrial Engineering and Engineering Management

Language:

English

Submitter:

Juliana Kathrin Zurbrügg

Date Deposited:

21 Jan 2020 11:34

Last Modified:

21 Jan 2020 11:34

BORIS DOI:

10.7892/boris.138877

URI:

https://boris.unibe.ch/id/eprint/138877

Actions (login required)

Edit item Edit item
Provide Feedback