Initializing help system before first use

A project planning model

A company has several projects that it must undertake in the next few months. Each project lasts for a given time (its duration) and uses up one resource as soon as it starts. The resource profile is the amount of the resource that is used in the months following the start of the project. For instance, project 1 uses up 3 units of resource in the month it starts, 4 units in its second month, and 2 units in its last month.

The problem is to decide when to start each project, subject to not using more of any resource in a given month than is available. The benefit from the project only starts to accrue when the project has been completed, and then it accrues at BENp per month for project p, up to the end of the time horizon. Below, we give a mathematical formulation of the above project planning problem, and then display the Mosel model form.

Model formulation

Let PROJ denote the set of projects and MONTHS={1,...,NM} the set of months to plan for. The data are:

DURp the duration of project p
RESUSEpt the resource usage of project p in its tth month
RESMAXm the resource available in month m
BENp the benefit per month when project finishes

We introduce the binary decision variables startpm that are 1 if project p starts in month m, and 0 otherwise.

The objective function is obtained by noting that the benefit coming from a project only starts to accrue when the project has finished. If it starts in month m then it finishes in month m+DURp-1. So, in total, we get the benefit of BENp for NM-(m + DURp-1) = NM - m - DURp+1 months. We must consider all the possible projects, and all the starting months that let the project finish before the end of the planning period. For the project to complete it must start no later than month NM-DURp. Thus the profit is:

∑
p ∈ PROJ
NM-DURp
∑
m = 1
(BENp · (NM-m-DURp+1)) · startpm

Each project must be done once, so it must start in one of the months 1 to NM-DURp:

∀ p ∈ PROJ:
∑
m ∈ MONTHS
startpm = 1

We next need to consider the implications of the limited resource availability each month. Note that if a project p starts in month m it is in its (k-m+1)th month in month k, and so will be using RESUSEp,k-m+1 units of the resource. Adding this up for all projects and all starting months up to and including the particular month k under consideration gives:

∀ k ∈ MONTHS:
∑
p ∈ PROJ
k
∑
m = 1
RESUSEp,k+1-m · startpm ≤ RESMAXk

Finally we have to specify that the startpm are binary (0 or 1) variables:

∀ p ∈ PROJ, m ∈ MONTHS: startpm ∈ {0,1}

Note that the start month of a project p is given by:

NM-DURp
∑
m = 1
m · startpm

since if an startpm is 1 the summation picks up the corresponding m.

Implementation

The model as specified to Mosel is as follows (file pplan.mos): 

model Pplan
 uses "mmxprs"

 declarations
  PROJ = 1..3                      ! Set of projects
  NM = 6                           ! Time horizon (months)
  MONTHS = 1..NM                   ! Set of time periods (months) to plan for

  DUR: array(PROJ) of integer      ! Duration of project p
  RESUSE: array(PROJ,MONTHS) of integer
                                   ! Res. usage of proj. p in its t'th month
  RESMAX: array(MONTHS) of integer ! Resource available in month m
  BEN: array(PROJ) of real         ! Benefit per month once project finished

  start: array(PROJ,MONTHS) of mpvar  ! 1 if proj p starts in month t, else 0
 end-declarations

 DUR   :: [3, 3, 4]
 RESMAX:: [5, 6, 7, 7, 6, 6]
 BEN   :: [10.2, 12.3, 11.2]
 RESUSE:: (1,1..3)[3, 4, 2]
 RESUSE:: (2,1..3)[4, 1, 5]
 RESUSE:: (3,1..4)[3, 2, 1, 2]     ! Other RESUSE entries are 0 by default

! Objective: Maximize Benefit
! If project p starts in month t, it finishes in month t+DUR(p)-1 and
! contributes a benefit of BEN(p) for the remaining NM-(t+DUR(p)-1) months:
 MaxBen:=
  sum(p in PROJ, m in 1..NM-DUR(p)) (BEN(p)*(NM-m-DUR(p)+1)) * start(p,m)

! Each project starts once and only once:
 forall(p in PROJ) One(p):= sum(m in MONTHS) start(p,m) = 1

! Resource availability:
! A project starting in month m is in its k-m+1'st month in month k:
 forall(k in MONTHS) ResMax(k):=
  sum(p in PROJ, m in 1..k) RESUSE(p,k+1-m)*start(p,m) <= RESMAX(k)

! Make all the start variables binary
 forall(p in PROJ, m in MONTHS) start(p,m) is_binary

 maximize(MaxBen)                   ! Solve the MIP-problem

 writeln("Solution value is: ", getobjval)
 forall(p in PROJ) writeln( p, " starts in month ",
                            getsol(sum(m in 1..NM-DUR(p)) m*start(p,m)) )
end-model

Note that in the solution printout we apply the getsol function not to a single variable but to a linear expression.

Parent Topic Integer Programming