A matheuristic-oriented iterated greedy algorithm for multi-mode resource-constrained project scheduling problem under uncertainty

Zheng Gao

doi:10.1016/j.cie.2024.110333

A matheuristic-oriented iterated greedy algorithm for multi-mode resource-constrained project scheduling problem under uncertainty

2024-07-01

0

PRE

AI

DOI：10.1016/j.cie.2024.110333

原文链接

原文求助

摘要

En 中文

Multi-mode resource-constrained project scheduling problem is one of the most important branches of combinatorial optimization problems. The aim is to find a feasible solution consisting of activity start time and execution mode so that the project makespan is minimized. However, there are a lot of uncertain events, that bring great challenges to project scheduling. We first propose a mixed integer linear programming model where the activity duration is uncertain. Then two uncertain parameters are introduced to describe the disturbance degree of uncertain activity duration and the allowable violation degree of constraints respectively, and the MILP model with uncertain activity duration is converted to its deterministic robust counterpart model. A matheuristic local optimization approach is proposed to balance computational time with the optimization of the computational result. A matheuristic-oriented iterated greedy algorithm that combines a matheuristic local optimization approach and an iterated greedy algorithm is proposed to solve this problem in this paper. Experimental results indicate that the robust counterpart model can obtain robust optimal solutions for small-scale instances in accepted computational time. Meanwhile, the proposed matheuristic-oriented iterated greedy algorithm can obtain robust near-optimal solutions for large-scale instances and is superior to other compared algorithms.

Keyword:

Project scheduling

Uncertainty

Robust counterpart model

Mixed integer linear programming

Matheuristic

A matheuristic-oriented iterated greedy algorithm for multi-mode resource-constrained project scheduling problem under uncertainty

摘要

期刊

机构

引用论文