Cumulative scheduling: discrete resources
The problem described in this section is taken from Section 9.4 `Backing up files' of the book `Applications of optimization with Xpress-MP'
Our task is to save sixteen files of the following sizes: 46kb, 55kb, 62kb, 87kb, 108kb, 114kb, 137kb, 164kb, 253kb, 364kb, 372kb, 388kb, 406kb, 432kb, 461kb, and 851kb onto empty disks of 1.44Mb capacity. How should the files be distributed in order to minimize the number of floppy disks used?
Model formulation
This problem belongs to the class of binpacking problems. We show here how it may be formulated and solved as a cumulative scheduling problem, where the disks are the resource and the files the tasks to be scheduled.
The floppy disks may be represented as a single, discrete resource disks, where every time unit stands for one disk. The resource capacity corresponds to the disk capacity.
We represent every file f (f ∈ FILES) by a task object filef, with a fixed duration of 1 unit and a resource requirement that corresponds to the given size SIZEf of the file. The `start' field of the task then indicates the choice of the disk for saving this file.
The objective is to minimize the number of disks that are used, which corresponds to minimizing the largest value taken by the `start' fields of the tasks (that is, the number of the disk used for saving a file). We thus have the following model.
tasks filesf (f ∈ FILES)
minimize diskuse
diskuse = maximumf ∈ FILES(filef.start)
disks.capacity = CAP
∀ f ∈ FILES: filef.start ≥ 1
∀ f ∈ FILES: filef.duration = 1
∀ f ∈ FILES: filef.requirementdisks = SIZEf
Implementation
The implementation with Xpress Kalis is quite straightforward. We define a resource of the type KALIS_DISCRETE_RESOURCE, indicating its total capacity. The definition of the tasks is similar to what we have seen in the previous example.
model "D-4 Bin packing (CP)"
uses "kalis"
declarations
ND: integer ! Number of floppy disks
FILES = 1..16 ! Set of files
DISKS: range ! Set of disks
CAP: integer ! Floppy disk size
SIZE: array(FILES) of integer ! Size of files to be saved
file: array(FILES) of cptask ! Tasks (= files to be saved)
disks: cpresource ! Resource representing disks
L: cpvarlist
diskuse: cpvar ! Number of disks used
end-declarations
initializations from 'Data/d4backup.dat'
CAP SIZE
end-initializations
! Provide a sufficiently large number of disks
ND:= ceil((sum(f in FILES) SIZE(f))/CAP)
DISKS:= 1..ND
! Setting up the resource (capacity limit of disks)
set_resource_attributes(disks, KALIS_DISCRETE_RESOURCE, CAP)
! Setting up the tasks
forall(f in FILES) do
setdomain(getstart(file(f)), DISKS) ! Start time (= choice of disk)
set_task_attributes(file(f), disks, SIZE(f)) ! Resource (disk space) req.
set_task_attributes(file(f), 1) ! Duration (= number of disks used)
end-do
! Limit the number of disks used
forall(f in FILES) L += getstart(file(f))
diskuse = maximum(L)
! Minimize the total number of disks used
if cp_schedule(diskuse) = 0 then
writeln("Problem infeasible")
end-if
! Solution printing
writeln("Number of disks used: ", getsol(diskuse))
forall(d in 1..getsol(diskuse)) do
write(d, ":")
forall(f in FILES) write( if(getsol(getstart(file(f)))=d , " "+SIZE(f), ""))
writeln(" space used: ",
sum(f in FILES | getsol(getstart(file(f)))=d) SIZE(f))
end-do
cp_show_stats
end-model
Results
Running the model results in the solution shown in Table Distribution of files to disks, that is, 3 disks are needed for backing up all the files.
| Disk | File sizes (in kb) | Used space (in Mb) |
|---|---|---|
| 1 | 46 87 137 164 253 364 388 | 1.439 |
| 2 | 55 62 108 372 406 432 | 1.435 |
| 3 | 114 461 851 | 1.426 |
Alternative formulation without scheduling objects
Instead of defining task and resource objects it is also possible to formulate this problem with a `cumulative' constraint over standard finite domain variables that represent the different attributes of tasks without being grouped into a predefined object. A single `cumulative' constraint expresses the problem of scheduling a set of tasks on one discrete resource by establishing the following relations between its arguments (five arrays of decision variables for the properties related to tasks—start, duration, end, resource use and size— all indexed by the same set R and a constant or time-indexed resource capacity):
∀ j ∈ R: usej · durationj = sizej
∀ t ∈ TIMES:
| ∑ |
| j ∈ R | t ∈ [UB(startj)..LB(endj)] |
where UB stands for `upper bound' and LB for `lower bound' of a decision variable.
Let savef denote the disk used for saving a file f and usef the space used by the file (f ∈ FILES). As with scheduling objects, the `start' property of a task corresponds to the disk chosen for saving the file, and the resource requirement of a task is the file size. Since we want to save every file onto a single disk, the `duration' durf is fixed to 1. The remaining task properties `end' and `size' (ef and sf) that need to be provided in the formulation of `cumulative' constraints are not really required for our problem; their values are determined by the other three properties.
Implementation
The following Mosel model implements the second model version using the cumulative constraint.
model "D-4 Bin packing (CP)"
uses "kalis", "mmsystem"
setparam("kalis_default_lb", 0)
declarations
ND: integer ! Number of floppy disks
FILES = 1..16 ! Set of files
DISKS: range ! Set of disks
CAP: integer ! Floppy disk size
SIZE: array(FILES) of integer ! Size of files to be saved
save: array(FILES) of cpvar ! Disk a file is saved on
use: array(FILES) of cpvar ! Space used by file on disk
dur,e,s: array(FILES) of cpvar ! Auxiliary arrays for 'cumulative'
diskuse: cpvar ! Number of disks used
Strategy: array(FILES) of cpbranching ! Enumeration
FSORT: array(FILES) of integer
end-declarations
initializations from 'Data/d4backup.dat'
CAP SIZE
end-initializations
! Provide a sufficiently large number of disks
ND:= ceil((sum(f in FILES) SIZE(f))/CAP)
DISKS:= 1..ND
finalize(DISKS)
! Limit the number of disks used
diskuse = maximum(save)
forall(f in FILES) do
setdomain(save(f), DISKS) ! Every file onto a single disk
use(f) = SIZE(f)
dur(f) = 1
end-do
! Capacity limit of disks
cumulative(save, dur, e, use, s, CAP)
! Definition of search (place largest files first)
qsort(SYS_DOWN, SIZE, FSORT) ! Sort files in decreasing order of size
forall(f in FILES)
Strategy(f):= assign_var(KALIS_SMALLEST_MIN, KALIS_MIN_TO_MAX, {save(FSORT(f))})
cp_set_branching(Strategy)
! Minimize the total number of disks used
if not cp_minimize(diskuse) then
writeln("Problem infeasible")
end-if
! Solution printing
writeln("Number of disks used: ", getsol(diskuse))
forall(d in 1..getsol(diskuse)) do
write(d, ":")
forall(f in FILES) write( if(getsol(save(f))=d , " "+SIZE(f), ""))
writeln(" space used: ", sum(f in FILES | getsol(save(f))=d) SIZE(f))
end-do
end-model
The solution produced by the execution of this model has the same objective function value, but the distribution of the files to the disks is not exactly the same: this problem has several different optimal solutions, in particular those that may be obtained be interchanging the order numbers of the disks. To shorten the search in such a case it may be useful to add some symmetry breaking constraints that reduce the size of the search space by removing a part of the feasible solutions. In the present example we may, for instance, assign the biggest file to the first disk and the second largest to one of the first two disks, and so on, until we reach a lower bound on the number of disks required (a save lower bound estimate is given by rounding up to the next larger integer the sum of files sizes divided by the disk capacity).