FIT5216: Modelling Discrete Optimization Problems

Assignment 3:  Service Scheduling

1 Overview

For this assignment, your task is to write a MiniZinc model for a given problem specification.

•  Submit your work to the MiniZinc auto grading system  (using the submit button in the MiniZinc IDE). You must submit via the IDE to be graded and receive marks.

•  Submit your model (copy and paste the contents of the .mzn file) and report using the Moodle assignment.

You have to submit by the due date (Friday 30th May 2025,  11:55pm), using MiniZinc and using the Moodle assignment, to receive full marks.  You can submit as often as you want before the due date.  Late submissions without special consideration receive a penalty of 10% per day. Submissions are not accepted more than 7 days after the original deadline.

This is an individual assignment. Your submission has to be entirely your own work. We will use similarity detection software to detect any attempt at collusion, and the penalties are quite harsh. Similarly you may not use generative AI such as ChatGPT, CoPilot or DeepSeek for any part of the project. Note that making your code available to other students undertaking the subject is also an instance of collusion that is also punishable. If in doubt, contact your teaching team with any questions!

2    Problem Statement

You are managing a service centre for hot water appliances.  Each week you are given a fixed set of services that have been booked. You need to assign the truck to visit and perform each service, while ensuring the trucks have the correct tools for the service and are regularly maintained.

The key data that you need to reason about is the scheduled services. They are represented by the MiniZinc data below:

int:  endtime;                                     %  latest  end  time  of  services

set  of  int:  TIME  =  0 . .endtime;

enum  SERVICE;                                     %  services  to  be  scheduled

array[SERVICE]  of  TIME:  start;   %  start  time  of  service

array[SERVICE]  of  TIME:  end;       %  end  time  of  service

enum  STYPE;                                        %  possible  service  types

array[SERVICE]  of  STYPE:  stype;  %  type  of  each  service

All the scheduling is over the fixed period from time 0 to endtime.  Each service has a fixed start and end time and a service type.

The key resource for undertaking the service scheduling are trucks.  They are represented in MiniZinc data below:

enum  TRUCK;                                           %  truck

TRUCK:  dtruck;                                     %  dummy  truck

enum  TTYPE  =  {  SML,  MED,  LRG,  DUMMY  };     %  truck  type

array[TRUCK]  of  TTYPE:  ttype;       %  type  of  each  truck

constraint  assert(forall(t  in  TRUCK)

(ttype[t]  =  DUMMY  <->  t  =  dtruck),"dummy  type  only  for  dtruck\n");

The trucks are given by the enumerated type TRUCK, but one of the elements of this type is a dummy truck dtruck.  Services assigned to the dummy truck are not actually performed.  Each truck has a truck type TTYPE. There is a dummy truck type which is only used for the dummy truck.

The  aim  of the  model  is  to  assign  services  to  trucks  so  that  as  many  services  as  possible are actually done, and minimize the amount of effort on maintenance.  Write a MiniZinc model service .mzn to tackle this problem. Its recommended that you tackle this problem in stages in the order shown. You can test your model before completing the entire assignment using the checker.

3    Stage A: Assigning Services

The core decisions of the model are, for each service which truck does that service.   Note that assigning a service to the dummy truck means that the service is not actually performed.

array[SERVICE]  of  var  TRUCK:  truck;  %  which  truck  takes  each  service:  dtruck  if  none

A first important constraint is that if two services are assigned to the same (non-dummy) truck then they cannot overlap in time.  Note that it is perfectly possible to assign two tasks to the same truck where the first has end time equal to the start time of the second task, e.,g the first task starts at 6 and ends at 8 (so duration 2) and the second starts at 8 and ends at 11 (so duration 3).

Given the data file below:

endtime  =  15;

SERVICE  =  {  S1,  S2,  S3,  S4,  S5,  S6,  S7,  S8,  S9,  S10  };

start  =          [0,    0,    0,   7,    3,    5,    6,  10,  11,    12];

end     =          [4,    5,    3,  11,    5,    8,    9,  12,  13,    15];

STYPE  =  {  Gas,  Roof,  Refit,  Solar  };

stype  =    [  Gas,  Refit,  Roof,  Gas,  Solar,  Solar,  Refit,  Roof,  Gas,  Refit  ];

TRUCK  =  {  DD,  T1,    T2,    T3,    T4,  T5  };

dtruck  =  DD;

ttype  =   [  DUMMY,  SML,  SML,  MED,  LRG,  MED  ];

Then a possible assignment of trucks is given by:

truck  =  [  T1,  T3,  T5,  T1,  T5,  T5,  T2,  T4,  T5,  T4  ];

which we can represent as

DD:

T1:S1  S4

T2:S7

T3:S2

T4:S8 S10

T5:S3 S5 S6 S9

which is visualized for each truck as

000000000011111

012345678901234

DD:............... 0

T1:####...####.... 8

T2:......###...... 3

T3:#####.......... 5

T4:..........##### 5

T5:########...##.. 10

Where we see the times when the truck is busy and the total work time for each truck.

4 Stage B: Truck Usage, Service Guarantee

Its not economical to use a truck for only very few services in the planning period.  We also have to offer a service guarantee to our client that some percentage of booked services will occur.  The data includes definitions:

int: minwork;       % minimal  percentage  of  time  each  truck  that  works  is  working

int: minservice;  % minimal  percentage  of  services  performed

For Stage B you need to ensure that any truck who is assigned any services is assigned work whose total duration is at least minwork% of endtime.  We also need to ensure that the percentage of services that are actually completed is at least minservice% of the services booked.

Assuming we set minwork  =  30 and minservice  =  80 a solution is:

DD:S5

T1:

T2:

T3:S3 S7

T4:S1 S6 S8 S10

T5:S2 S4 S9

with visualization:

000000000011111

012345678901234

DD:...##.......... 2

T1:............... 0

T2:............... 0

T3:###...###...... 6

T4:####.###..##### 12

T5:#####..######.. 11

Notice the trucks that were assigned very little work have disappeared. In this solution not every service is performed (S5 is not), but more than 80% of services are performed.

5 Stage C: Work Types

There are four types of maintenance services that can be booked:  Gas, Roof, Refit and  Solar, but trucks cannnot be neessarily configured to be able to perform all services. There is a limit on the number of types of service for each truck given by

array[TTYPE]  of  int: maxsty;         % max  service  types  for  each  truck  type

For the running example we assume maxsty  =  [1,2,3,0]; then a solution that satisfies this con- straint is

DD:S9  S10

T1:S3  S8

T2:S2  S7

T3:S5  S6

T4:S1  S4

T5:

visualized as:

000000000011111

012345678901234

DD: . . . . . . . . . . .####      5  {Gas,  Refit}

T1:### . . . . . . .## . . .      5  {Roof}

T2:#####.### . . . . . .     8  {Refit}

T3: . . .##### . . . . . . .      5  {Solar}

T4:#### . . .#### . . . .      8  {Gas}

T5: . . . . . . . . . . . . . . .     0  {}

The kinds of services for each truck are listed afterward. You can see that the SML trucks T1 and T2 only do one kind of service as required, in fact every truck only does one kind of service.  The dummy truck of course can be assigned all possible services.

If you  only  finish  to  this  stage  you  will  be  unable  to  acheive  more  than  30%  marks  for  most instances.   But  to  do  this  you  probably  need to  set the  maintenance  variables  mt  and  ms  below  to some good default values.

6 Stage D: Maintenance

Now we get into the more challenging part of the assignment.  We also have to ensure that we maintain the trucks, which means that we need to schedule maintenance tasks for them. The data and decisions are defined by:

enum  MAINTYPE  =  {  NO,  SH,  LG,  MJ  };  %  NO means  no maintenance

array[MAINTYPE]  of  int: maintdur;  %  duration  of maintenance

array[MAINTYPE]  of  int: maxsep;     %  max  elapsed  time  since  last maint  this  type  or  higher constraint  assert(maintdur[NO]  =  0  /\ maxsep[NO]  =  0,  "rules  for  empty maintenance\n");

int: maxmaint;

set  of  int:  MAINT  =  1 . .maxmaint;

array[TRUCK,MAINT]  of  var  MAINTYPE: mt;  % maintenance  for  each  truck  (NO=not  used) .

array[TRUCK,MAINT]  of  var  TIME: ms;         %  maintenance  start  time  for  each  truck

So each truck can have up to maxmaint maintenances in the schedule.  The maintenances are SH (short), LG (long), MJ (major) and NO (none) which is a placeholder for no maintenance used.

The duration of each maintenance task is defined in the array maintdur.

For each truck we have to decide the type mt of each maintenance, and the start time ms of each maintenance.  All the NO maintenances should be at the end of the list for each truck.  The ms start time for NO maintenances is irrelevant. The other maintenances must appear in order of increasing start time, the earliest first, then the next, etc.

The maintenance constraints are defined as follows:

•  A truck assigned no services needs no maintenance. The remaining constraints apply to any trucks assigned a service.

•  There must be a SH/LG or MJ maintenance within maxsep[SH] of the start of the schedule and within maxsep[SH] of the end of any maintenance task, unless this falls outside TIME (i.e. starts at endtime or later).

•  There must be a LG or MJ maintenance within maxsep[LG] of the start of the schedule and within maxsep[LG] of the end of any LG or MJ maintenance task, unless this falls outside TIME.

The other important constraint is that maintenance tasks and service tasks for the same truck cannot overlap.

Given the data

maxmaint  =  2;

maintdur  =  [0,1,3,5];

maxsep  =  [0,5,10,0]; A solution might be

truck  =  [T2,  T1,  DD,  T2,  T3,  T3,  T1,  DD,  T3,  T1]; mt  =

[|  DD:  NO,  NO |   T1:  SH,  LG

|   T2:  LG,  LG

|   T3:  LG,  LG

|   T4:  NO,  NO

|  T5:  NO,  NO |];

ms  =

[|  DD:  0,    0

|  T1:  5,    9

|  T2:  4,  12

|  T3:  0,    8

|  T4:  0,    0

|  T5:  0,    0

|];

which is visualized as

000000000011111

012345678901234

DD:### . . . . . . .## . . .      5  {Roof}

T1:#####m###mmm###    11  {Refit}

T2:####mmm####.mmm      8  {Gas}

T3:mmm#####mmm## . .      7  {Gas,  Solar}

T4: . . . . . . . . . . . . . . .     0  {}

T5: . . . . . . . . . . . . . . .     0  {}

We can see that no maintenance overlaps with service tasks, the start times for each truck are ordered, and the NO maintenances appear at the end.  Clearly there is a maintenance within the first 5 time steps for all used trucks, and no period without maintenance for 5 time steps (i.e. for T3 its last maintenance ends at 11 which is within 5 time steps of the endtime 15), and a large maintenance within the first 10 steps for all used trucks.

7 Stage E: Objective

The main criteria for optimisation are two:

• Maximizing the total duration of services performed.

•  Minimizing the total maintenance load.  The maintenance load at time t is defined by the square of the number of simultaneous maintenance tasks occurring at that time  (started at or before t and ending after t.   The  total maintenance load is the sum over all times 0..endtime-1.

You should write your model to first minimize the total maintenance load, and then maximize the total duration of services performed.

An optimal solution for the data show service0 .dzn is given by

truck  =  [DD,  T3,  T4,  T4,  T5,  T5,  DD,  T3,  T5,  T4]; mt  =

[|  DD:  NO,  NO |  T1:  NO,  NO

|   T2:  NO,  NO

|   T3:  LG,  SH

|   T4:  LG,  SH

|   T5:  SH,  LG |];

ms  =

[|  DD:  0,    0

|  T1:  0,    0

|  T2:  0,    0

|  T3:  5,  12

|  T4:  3,  11

|  T5:  2,    8

|];

with visualization

000000000011111

012345678901234

DD:#### . .### . . . . . .      7  {Gas,  Refit}

T1: . . . . . . . . . . . . . . .     0  {}

T2: . . . . . . . . . . . . . . .     0  {}

T3:#####mmm . .##m . .      7  {Roof,  Refit}

T4:###mmm.####m###    10  {Gas,  Roof,  Refit}

T5: . .m#####mmm## . .      7  {Gas,  Solar}

which has total maintenance load of 14 (1 active maintenance at times 2,3,4,6,7,8,9,10,11,12 = 10 load, and 2 active maintenances at time 5 = 4 load) and total service duration 24.

If you  only finish  to  this  stage  you  will  be  unable  to  acheive  more  than  75%  marks  for  some instances.

8    Challenge Stage F: Major Maintenance

The remaining difficulty is to schedule major maintenances.  Major maintenances are required on a truck every time it has performed majorwork time units of service tasks.  The data to support this is defined by

int: majorwork;                               % max  work  allowed  before major maintenance

array[TRUCK]  of  int:  prework;     %  units  of  work  since  last major maintenance

For each truck t we are given the amount of work they have done before the scheduling period, since the last major maintenance prework[t].  We must ensure that no truck performs more than majorwork time units of service since its last major maintenance, anywhere in the schedule.  For long schedules we may need to include more than one major maintenance for a truck.

Given data

majorwork  =  30;

prework  =  [  0,  5,  10,  15,  20,  25  ];

the previous solution is no longer valid since T5 is assigned 7 more time units of service, which added to its 25 would lead to 32 without a major maintenance.  Hence the best schedule changes to

truck  =  [T4,  T1,  T3,  DD,  T3,  T4,  T1,  T3,  DD,  T4]; mt  =

[|  DD:  NO,  NO |   T1:  SH,  LG

|   T2:  NO,  NO

|   T3:  LG,  SH

|   T4:  SH,  LG

|  T5:  NO,  NO |];

ms  =

[|  DD:  0,    0

|  T1:  5,  10

|  T2:  0,    0

|  T3:  5,  13

|  T4:  4,    8

|  T5:  0,    0

|];

visualized as

000000000011111

012345678901234

DD: . . . . . . .###### . .      6  {Gas}

T1:#####m### .mmm . .      8  {Refit}

T2: . . . . . . . . . . . . . . .     0  {}

T3:#####mmm . .## .m .      7  {Roof,  Solar}

T4:####m###mmm.###    10  {Gas,  Refit,  Solar}

T5: . . . . . . . . . . . . . . .     0  {}

where we have stopped using T5 and used other trucks which have less prework. The maintenance load is 16 and service time is 25.

Note that this constraint can be tackled using the ideas of sequence dependent scheduling.

Stage G: Report

Obviously the data format for this problem is very complex.  There are many implicit assumptions that are likely to hold for realistic data.  But we need to be prepared for strange data.  Consider the following conditions on the inputs to your model, for each of them explain in a paragraph what your model will do in these circumstances, and more importantly, why:

• minservice  =  0.

• minservice  =  100.

• minwork  =  0.

• minwork  =  100.

• maxsty  =  [1,1,1,0].

• maintdur[SH]  > maintdur[LG].

• maxsep[SH]  >  maxsep[LG].

• maxsep[MJ]  >  maxsep[LG].

• maxsep[SH]  = maxsep[LG]  =  endtime.

• prework  =  [0  |  t  in  TRUCK].

• majorwork  >  endtime.

• maxsty[ty]  =  0 for some ty other than DUMMY

• start[s]  =  0 and end[s]  =  endtime for some service s.

•  start includes k services with the same start and end time where k = card(TRUCK).

• card(STYPE)  =  1

You will probably need to experiment by generating new data files.   Note  that  some  of these scenarios will have little or no effect, and some will have large and/or obvious effects. You will have to refer to other data values as well to explain some of these conditions.  Do your best to explain why the change, or lack of change, results.

After explaining all the cases above, give a summary of what you think are the most important constraints in the model; i.e.  those that are most changing the form of the answer.  Justify your answer. The report should use no more than 4 A4 pages.

9 Instructions

Edit the provided mzn model files to solve the problems described above.  You are provided with some sample data files to try your model on. Your implementations can be tested locally by using the Run+check icon in the MiniZinc IDE. Note that the checker for this assignment will only test whether your model produces output in the required format, it does not check whether your solutions are correct.  The grader on the server will give you feedback on the correctness of your submitted solutions and models.

10 Marking

You will get a maximum of 50 marks for this assigment which is worth 25% of the units overall marks.  Part of the marks are automatically calculated.  The submission has  10 marks for locally tested data and 20 marks for model testing, for a total of 30 marks by automatic calculation. You will only get full marks if you implement all stages.

The 20 remaining marks are given for code comments and the report marked by the tutors, with the following allocation: Code Comments (6 marks) Report (14 marks).

For the autograded part of the marking you can get most marks having implemented Stages A-E only.  Stage F is optional, without implementing it there will be some instances where you can get a maximum of 3/4 of the marks available.

Code commenting should clear explain the role of each variable, constraint and objective defined in the model. You should explain how every constraint is modelled unless this is straightforward: e.g. adding that we use alldifferent to ensure all of a set are different is unnecessary detail. You should use good identifier names for variables and procedures you define to help readability.  The code and the comments must be formatted to be easy to read and comprehend.

The report requires a discussion of a number of forms of input to the model.  Make sure its easy for the reader to determine what everything in this discussion refers to.  The written report is worth 14 marks and should answer the questions listed in Stage G. The explanations should be clear and easy to interpret.  If you wish you can support your explanation of the reasons for the change or lack thereof by referring to the results of experiments you conducted, but that by itself is not enough to explain behaviour.