Project scheduling with processing time compression cost and lateness penalties

Byung-Cheon Choi and Dirk Briskorn

No 651, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre

Abstract: We consider a project scheduling problem where the precedence constraints graph is an out-tree. The processing times can be compressed by using additional resources, which causes cost and simultaneously reduces the processing times of jobs. The objective is to minimize the sum of total lateness penalties and total compression costs where the cost function for compressing the processing times is linear in the amount of compression. The problem can be decomposed into two types of subproblems. We show that both subproblems can be solved in polynomial time. Using these results, we show that the main problem is solvable in polynomial time if the number of chains in the out-tree is fixed.

Keywords: Project scheduling; controllable processing times; convex programming; shortest path problem (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/147569/1/manuskript_651.pdf (application/pdf)

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:zbw:cauman:651

Access Statistics for this paper

More papers in Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics ().