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

Abstract

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 flows. 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.