An efficient metaheuristic to solve the project portfolio selection and scheduling problem for industrial projects

Abstract

Industrial companies aim for optimizing profit from delivering project outcomes. Maximizing profit relies on optimization of using resources, production capacity and available time. To reach this goal, companies are typically reliant on planning and production schedules. This problem is known as the project portfolio selection and scheduling problem (PPSSP). The PPSSP can be solved using an integer linear programming (ILP). However, solving an ILP for complex cases with a large number of variables takes a lot of time. Solving the PPSSP using a heuristic method provides a good alternative. Due to the structure, an adapted version of variable neighborhood search (VNS) is chosen as heuristic method. The adapted VNS is combined with tabu search to obtain an alternative for solving the ILP. The solution obtained with the heuristic method is represented as an activity list which is a specified order of planning tasks. The schedule which is represented by the activity list can be obtained using the serial schedule generation scheme (SGS). Serial SGS represents every optimal schedule in the non-preemptive case. When preemption is allowed, schedules might not be represented by an activity list in all cases. The overall profit of the optimal schedule is never smaller than in the non-preemptive case. Because of this, a solution is represented by a selection and an activity list from which the schedule can be obtained through using the preemptive serial SGS. The heuristic is used to obtain some results for less complex instances which are compared to the results obtained by solving the ILP. In some cases, the ILP could not solve the problem in a short time span. It turns out that the performance of the adapted VNS in combination with tabu search provides good estimates close to the real optimum.