An Ecient Merge Search Matheuristic for Maximising the Net Present Value of Project Schedules Dhananjay R. Thiruvadya Su Nguyenb Christian Blumc Andreas T. Ernstd

2025-04-30 0 0 548.48KB 17 页 10玖币

侵权投诉

An Eﬃcient Merge Search Matheuristic for Maximising the Net

Present Value of Project Schedules

Dhananjay R. Thiruvadya, Su Nguyenb, Christian Blumc, Andreas T. Ernstd

aSchool of Information Technology, Deakin University, Geelong, Australia

bCentre for Data Analytics and Cognition, La Trobe University, Australia

cArtiﬁcial Intelligence Research Institute (IIIA-CSIC), Bellaterra, Spain

dSchool of Mathematical Sciences, Monash University, Australia

October 21, 2022

Abstract

Resource constrained project scheduling is an important combinatorial optimisation problem

with many practical applications. With complex requirements such as precedence constraints, lim-

ited resources, and ﬁnance-based objectives, ﬁnding optimal solutions for large problem instances

is very challenging even with well-customised meta-heuristics and matheuristics. To address this

challenge, we propose a new math-heuristic algorithm based on Merge Search and parallel comput-

ing to solve the resource constrained project scheduling with the aim of maximising the net present

value. This paper presents a novel matheuristic framework designed for resource constrained project

scheduling, Merge search, which is a variable partitioning and merging mechanism to formulate re-

stricted mixed integer programs with the aim of improving an existing pool of solutions. The

solution pool is obtained via a customised parallel ant colony optimisation algorithm, which is also

capable of generating high quality solutions on its own. The experimental results show that the pro-

posed method outperforms the current state-of-the-art algorithms on known benchmark problem

instances. Further analyses also demonstrate that the proposed algorithm is substantially more

eﬃcient compared to its counterparts in respect to its convergence properties when considering

multiple cores.

1 Introduction

Project scheduling has been a problem of interest for many years. There are a number of variants, but

the main aspect of the problem is to complete several tasks with an objective associated with the total

completion time or, in other words, the cumulative value of tasks. The project scheduling problem

has a number of variants [Brucker et al., 1999]. The common aspects of all of these variants are that

the projects consist of tasks, shared renewable resources (with limits) and a deadline. There might

be precedence constraints between the tasks. Moreover, tasks use some proportion of the available

resources. To solve these problems, several diﬀerent methods have been proposed. These include

heuristics, meta-heuristics (simulated annealing, genetic algorithms, tabu search, etc.), and branch &

bound. A number of these approaches (heuristics, meta-heuristics and exact techniques) and their

associated details were discussed by Demeulemeester and Herroelen [2002] and Neumann et al. [2003].

Furthermore, Neumann et al. [2003] discuss heuristic and exact approaches for project scheduling with

time windows.

An important variant of project scheduling is the resource constrained project scheduling (RCPS)

with the net present value (NPV) objective (RCPS-NPV) [Kimms, 2001]. In this problem, all tasks

are associated with a cash ﬂow, either positive or negative, and the goal is to maximise the NPV, i.e.

the sum of the discounted cash ﬂows of the tasks. This problem has received a lot of attention recently

as it reﬂects the ﬁnancial health or feasibility of a project. RCPS-NPV is a very complex problem for

which several diﬀerent approaches have been proposed. Chen et al. [2010] investigate the problem with

98 tasks using ant colony optimisation (ACO), outperforming other meta-heuristic methods including

arXiv:2210.11260v1 [cs.NE] 20 Oct 2022

simulated annealing, genetic algorithms and tabu search. Show [2006] also investigate the use of ACO

and show that their approach is eﬀective for problem instances with up to 50 tasks. Vanhoucke [2010]

propose a scatter search heuristic, which outperforms a branch & bound method previously developed

by the same authors for the same problem [Vanhoucke et al., 2001]. Gu et al. [2013] suggest the use

of constraint programming within a Lagrangian relaxation framework in order to ﬁnd high-quality

feasible solutions to the problem. In a similar fashion, Thiruvady et al. [2014] developed a hybrid of

Lagrangian relaxation and ACO, which was shown to be very eﬀective, particularly when implemented

in a parallel setting [Brent et al., 2014].

Construct, solve, merge and adapt (CMSA) is a method that was recently introduced and applied

to a number of combinatorial optimisation problems [Blum et al., 2016, Blum and Blesa, 2016, Blum,

2016, Lewis et al., 2019, Polyakovskiy et al., 2020, Thiruvady et al., 2020, Thiruvady and Lewis,

2022]. Blum et al. [2016] introduced this method and applied it to two problems, namely the mini-

mum common string partition problem and the minimum covering arborescence problem. Blum and

Blesa [2016] then showed that CMSA is eﬀective on the repetition-free longest common subsequence

problem, and Blum [2016] showed the same for the unbalanced common string partition problem. The

CMSA method works as follows. There are four stages to the algorithm: (a) generate a number of

‘good’ solutions and add the components found in these solutions to a pool of solution components,

(b) identify a restricted mixed integer program (MIP) based on the pool of solution components, (c)

solve the MIP to generate a ‘merged’ solution, and (d) update the pool of solution components by in-

corporating information from the MIP. The above stages are iteratively applied until some termination

criteria are reached. Thiruvady et al. [2019] proposed a hybrid of CMSA and parallel ACO for RCPS-

NPV, which produces the currently best results in the literature. Polyakovskiy et al. [2020] apply

CMSA to a just-in-time batch scheduling problem, with promising results. The study by Thiruvady

et al. [2020] show that CMSA is eﬀective in tackling a resource constrained job scheduling problem.

Most recently, Thiruvady and Lewis [2022] combine CMSA with Tabu search for the maximum happy

vertices problem, and they ﬁnd that the hybrid produces excellent results.

Merge search is a very recent technique proposed for a range of scheduling problems [Kenny et al.,

2018]. The algorithm is similar to that of CMSA, where presumably good solutions are used to generate

a restricted MIP, which in turn, is solved to obtain a solution that is used as the input to generate

a new pool of solutions. The key diﬀerences are in how the restricted MIP is generated and how

its solution space may be eﬃciently improved to incorporate more diversity (via a random splitting

mechanism). The restricted MIP in Merge search is generated by an aggregation of variables (details

in Section 3), depending on a pool of solutions. Random splitting is now applied to the aggregated

MIP, where the aggregated variable sets are split to allow a larger neighbourhood to be searched.

Relatively few studies have been conducted with Merge search, but the existing ones shown excellent

results. Kenny et al. [2018] showed that Merge search is very eﬀective for the constrained pit problem.

Merge search has two key advantages over conventional methods such as genetic algorithms

[Mitchell, 1998]. Firstly, it is able to manage the trade-oﬀ of solving a straightforward MIP (via

variable aggregation) but yet consider a substantially diverse search space obtained by merging so-

lution components from a very large population of solutions. Secondly, the method is inherently

parallelisable, lending itself to multi-core shared memory architectures [Dagum and Menon, 1998] or

the message passing interface (MPI) [Gropp et al., 1994]. Indeed, parallel ACO (PACO) [Thiruvady

et al., 2016] and a parallel hybrid of ACO and constraint programming [Cohen et al., 2017] has shown

to be very eﬀective on a related resource constrained job scheduling problem. By exploiting the relative

advantages of Merge search and PACO, this study tackles the RCPS-NPV, thereby further validating

this technique for scheduling.

In this study we propose an eﬃcient Merge search algorithm with PACO (MS-PACO) for tackling

the RCPS-NPV problem. An eﬃcient practical implementation of MS-PACO is achieved through

a tight coupling between the MIP component and PACO, where PACO provides good areas of the

search space for the MIP to explore, and in turn, the MIP provides improvements which are used in

the learning component of PACO. In particular, this framework is eﬃcient because (i) a solution pool

with large diversity can be obtained quickly, (ii) the search space can be enlarged eﬃciently via random

splitting and (iii) restricted MIPs can be solved in short time-frames. We demonstrate the eﬃcacy

of MS-PACO on a large number of RCPS-NPV instances, where it outperforms previous algorithms,

especially the most recent one involving CMSA and PACO [Thiruvady et al., 2019]. Overall, the

contributions of this study can be summarised as follows:

•Regarding PACO: we provide an eﬃcient implementation of PACO, which is very eﬀective at

generating a set of diverse and quality solutions.

•Regarding the combination of Merge search with PACO: we introduce a new variable partitioning

and merging mechanism to formulate restricted MIPs to further improve solutions for the RCPS-

NPV.

•We present an eﬃcient way to utilise the high-quality solutions found by PACO to improve them

via a restricted MIP.

•Regarding results: our algorithm obtains improvements of best-known-solutions for numerous

RCPS-NPV benchmark instances.

The paper is organized as follows. Section 2 formally discusses the RCPS-NPV problem and

provides an eﬃcient MIP model. Section 3 discusses Merge search and PACO, including the intuition

behind the methods and their integration. Section 5 details the experiments conducted and the results

obtained from these experiments. This includes an analysis of the algorithms on known benchmark

problem instances and an analysis of the algorithm’s convergence characteristics. Section 6 concludes

the paper and provides potential future direction.

2 Formulating the RCPS-NPV Problem

The formal deﬁnition of the RCPS-NPV problem is as follows. Given is a set Jcontaining ntasks.

Each task i∈ J has a duration di, a resource consumption rik for each of kresources, and a cash ﬂow

cfit, which depends on the time period t≥1. The cash ﬂows may be positive or negative. Moreover,

the cash ﬂow of a task may vary over its duration. Its total net value ci, however, can be calculated if

it would be completed at time point 0. Using this value we can determine a discounted value for future

time points by applying a discount factor α > 0 to the start time siof the task. We use cie−α(si+di)

[Kimms, 2001], where diis task i’s duration. Note that the discount formula e−α t is equivalent to the

commonly used function 1/(1 + ¯α)tfor some ¯α. We are also given a set of precedence constraints P,

where i→jor (i, j)∈ P ⊆ J × J represents that task ineeds to complete before jstarts.

For the kresources we are given limits R1, . . . , Rk, and the cumulative use of the resources by the

tasks at all time points must satisfy these limits. Finally, we are given δ, which is the deadline for all

tasks and, therefore, the time horizon to complete the project. This deadline ensures that tasks with

a negative cash ﬂow and no successors will still be completed. The objective is to maximise the NPV

and the problem can then formally be stated as follows:

max X

i∈J

cie−α(si+di)(1)

S.T. si+di≤sj∀(i, j)∈P(2)

i∈S(t)

rim ≤Rm∀m= 1,...k (3)

0≤si≤δ−di∀i∈ J (4)

S(t) is the set of tasks executing at time t. Function (1) is the NPV objective, which is very

challenging to solve as it is non-linear and neither convex nor concave. Constraints (2) ensure that the

precedence constraints are satisﬁed. Constraints (3) enforce the resource limits and Constraints (4)

ensure that the deadline is not violated.

Similar to the studies by Kimms [2001] and Thiruvady et al. [2014], we will consider deadlines that

are relatively loose, since minimizing the makespan is not an objective. This results in suﬃcient slack

which allows negative-valued tasks to be scheduled later, thereby increasing the NPV slightly.

2.1 An Integer Programming Model

An integer programming (IP) model for the RCPS-NPV problem is given by Kimms [2001]. However,

the study by Thiruvady et al. [2014] showed that this model can be made computationally more

eﬃcient. Hence, we use the latter model as the basis for this study.

The improved model can be deﬁned as follows: Let xit be a binary variable for each task i∈ J

and time point t∈ {1, . . . , δ}.xit takes value 1 if task ihas already completed by time point t. The

MIP model can then be stated as follows:

max X

i∈J

t=2

cie−αt (xit −xit−1) (5)

Subject to

xit ≥xit−1∀i∈ J, t ∈ {2, . . . , δ}(6)

xiδ = 1 ∀i∈ J (7)

xi,t = 0 ∀i∈ J, t ∈ {1, . . . , dj−1}(8)

xjt ≤xi,t−dj∀(i, j)∈ P, t ∈ {dj+ 1, . . . , δ}(9)

i∈J :

di>t

rik (xit −xi,t−di)≤Rmt ∀m={1, . . . , k},

t∈ {1, . . . , δ}(10)

xit ∈ {0,1} ∀ i∈ J, t ∈ {1, . . . , δ}(11)

Equation (5) is the objective, aiming to maximise the NPV. Constraints (6) ensure that once a

task is completed it stays completed. Constraints (7) ensure that all tasks complete. Constraints (9)

ensure that all precedence constraints are satisﬁed. Constraints (10) require that, at each time point,

none of the resource limits are exceeded. Finally, the variables xit are binary.

This formulation often results in a high density of variables with one-zero values. As we will shortly

see, this proves extremely beneﬁcial when applying MS-PACO to this problem. We also note that for

MS-PACO we never solve the complete model. Instead, by signiﬁcantly restricting the set of feasible

time points, we solve substantially reduced subproblems. In preliminary experimentation we found

that such MIPs can be easily solved with a general-purpose MIP solver.

3 The Proposed Algorithm

In this section, we focus on MS-PACO and its particular implementation for the RCPS-NPV. Using an

initial pool of (good) solutions, this algorithm generates an aggregated MIP, that is eﬃciently solved

by a general-purpose MIP solver. The initial solutions themselves are found by running multiple

colonies of ACO in a parallel setting, as discussed in [Thiruvady et al., 2012]. Solutions in future

iterations are also found by this method.

We ﬁrst discuss the parallel ACO (PACO) approach. Compared to previous multi-threaded im-

plementations of ACO for this and similar resource constrained scheduling problems, we implement a

multi-colony ACO. In this approach the colonies share—at regular intervals—information on their best

solution. This approach, in its own right, proves eﬀective on small problem instances (see Section 5).

This is followed by a discussion of Merge Search and its integration with PACO. As previously

discussed, Merge Search requires a population of solutions which are of high quality and which are

characterised by suﬃcient diversity. A key requirement for the generation of this population is that

this is done eﬃciently, and hence, PACO provides an ideal way to achieve this. This population is

used to build an aggregated model or restricted MIP, which can be solved very eﬃciently compared to

the original MIP. The outputs of the MIP are passed back into PACO, which is used to build a new

population. Our results show that this approach is indeed very eﬀective for the RCPS-NPV problem,

achieving best results for a number of problem instances (see Section 5).

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

AnEcientMergeSearchMatheuristicforMaximisingtheNetPresentValueofProjectSchedulesDhananjayR.Thiruvadya,SuNguyenb,ChristianBlumc,AndreasT.ErnstdaSchoolofInformationTechnology,DeakinUniversity,Geelong,AustraliabCentreforDataAnalyticsandCognition,LaTrobeUniversity,AustraliacArticialIntelligenceResearc...

展开>> 收起<<

An Ecient Merge Search Matheuristic for Maximising the Net Present Value of Project Schedules Dhananjay R. Thiruvadya Su Nguyenb Christian Blumc Andreas T. Ernstd.pdf

共17页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

An Ecient Merge Search Matheuristic for Maximising the Net Present Value of Project Schedules Dhananjay R. Thiruvadya Su Nguyenb Christian Blumc Andreas T. Ernstd

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: