A Metaheuristic Approach to the Resource Constrained Project Scheduling with Variable Activity Durations and Convex Cost Functions

Koji Nonobe () and Toshihide Ibaraki ()
Additional contact information
Koji Nonobe: Hosei University
Toshihide Ibaraki: Kwansei Gakuin University

Chapter Chapter 9 in Perspectives in Modern Project Scheduling, 2006, pp 225-248 from Springer

Abstract: Abstract We introduce a generalized model of the resource constrained project scheduling problem (RCPSP). It features that (i) the duration of an activity is not constant, but can vary in a specified range, and (ii) the objective is to minimize a convex function of time-lag costs, where a time-lag cost is charged according to the difference between the start/completion times of activities. These features achieve the flexibility of the model. It is known that, in the RCPSP, resource constraints can be replaced by some precedence constraints appropriately defined between the activities that require a common scarce resource. If we remove resource constraints by precedence constraints, our problem can be formulated as the dual problem of a minimum cost flow problem, and thus can be solved efficiently. Exploiting this property, we design a heuristic algorithm based on local search. We conducted computational experiments with benchmark instances to minimize the weighted earliness-tardiness costs, as well as instances in which activity-crashing or relaxation of temporal constraints are allowed. These results indicate the usefulness of our generalized RCPSP model and the proposed algorithm.

Keywords: Resource constrained project scheduling; convex objective functions; variable activity durations; metaheuristics (search for similar items in EconPapers)
Date: 2006
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:isochp:978-0-387-33768-5_9

Ordering information: This item can be ordered from
http://www.springer.com/9780387337685

DOI: 10.1007/978-0-387-33768-5_9

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().