A linear programming based method for the resource constrained multiproject scheduling problem with weighted earliness/tardiness costs

Pamay, Mehmet Berke (2011) A linear programming based method for the resource constrained multiproject scheduling problem with weighted earliness/tardiness costs. [Thesis]

[thumbnail of MehmetBerkePamay_408714.pdf] PDF

Download (1MB)


This study addresses the Resource Constrained Multi Project Scheduling Problem with Weighted Earliness Tardiness Costs (RCMPSPWET). In multi-project environments, the project portfolio of a company does often change dramatically in time. In this dynamic context, the arrival of a new project requires quoting a due date while keeping the disruptions to the existing plans and schedules to a minimum. The suggested solution method is an adaptation of the well known shifting bottleneck (SB) heuristic in the job shop literature. Initially, a base schedule is obtained by relaxing all resource capacities and solving the resulting model as a linear program (LP). The SB heuristic then resolves the resource conflicts present in the optimal solution of this resource relaxation iteratively by solving a set of single-resource weighted earliness tardiness scheduling subproblems with precedence constraints. The unit earliness and tardiness costs in the subproblems are estimated by drawing upon tools from LP sensitivity analysis recently proposed by Bülbül and Kaminsky [1] for a general job shop scheduling problem. The subproblems in the SB heuristic are a generalization of the NP-hard single machine weighted earliness tardiness problem, and a neighborhood search based algorithm is applied to these for the efficiency of the overall SB algorithm. The solution of a subproblem introduces new precedence relationships based on the concept of resource ows. These new precedence constraints are incorporated into the LP mentioned above and ensure that the capacity of the resource under consideration is observed. These steps are repeated until all resource conflicts are removed. The order in which the resource conflicts are resolved is a major determinant of the final solution quality, and therefore, a systematic tree search strategy is implemented for resolving the resource conflicts in different orders. A local search algorithm for the original problem is also adopted to benchmark the results.
Item Type: Thesis
Uncontrolled Keywords: Multi-project scheduling. -- Weighted earliness/tardiness. -- Dynamic scheduling. -- Project scheduling. -- Project changes. -- Project cost. -- Çoklu proje çizelgeleme. -- Erkenlik geçlik. -- Devingen çizelgeleme. -- Proje çizelgeleme. -- Proje değişiklikleri. -- Proje maliyeti.
Subjects: T Technology > TA Engineering (General). Civil engineering (General)
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 06 Jul 2014 01:15
Last Modified: 26 Apr 2022 10:01
URI: https://research.sabanciuniv.edu/id/eprint/24312

Actions (login required)

View Item
View Item