Profit maximising job scheduling using Python

Question

I have a scheduling scenario in which every time period has a cost. I need to select the time periods which will give me the least cost over a period of 24 hours. See below for an example of the date set.

Start time | End time | Cost

• 00:00 | 01:00 | $30
• 01:00 | 05:00 | $50
• 02:00 | 08:00 | $70
• 04:00 | 12:00 | $100
• 08:00 | 11:00 | $60
• 10:00 | 14:00 | $50
• 13:00 | 17:00 | $90
• 13:00 | 20:00 | $120
• 16:00 | 23:00 | $80
• 18:00 | 22:00 | $60
• 19:00 | 20:00 | $50
• 21:00 | 23:00 | $20

What I want is a Python solution to derive the set of time periods which gives the least cost, each time period must not overlap and they must all add up to 24 hours.

Answer 1

Here is an example of how to implement this as Set Partitioning problem using a MIP (Mixed-Integer Programming) model.

I generated the following random data:

----     14 PARAMETER data  input data

          start      length        cost

i1            2           5          47
i2           19           5          20
i3           11           2          38
i4            5           2          14
i5            5           8          40
i6            3          10          26
i7            6           3          68
i8           19           5          61
i9                       10          80
i10          10           4          37
i11          22           2          70
i12          12           7          78
i13          22           2          67
i14          17           7          35
i15           1           4          17
i16          13           4          19
i17           1           8          68
i18           4           9          59
i19          14           8          12
i20           8           6          82

From this data we can construct a boolean coverage matrix, indicating if item i covers hour t.

----     14 PARAMETER cover  coverage of hours by items

            h00         h01         h02         h03         h04         h05         h06         h07         h08

i1                                    1           1           1           1           1
i4                                                                        1           1
i5                                                                        1           1           1           1
i6                                                1           1           1           1           1           1
i7                                                                                    1           1           1
i9            1           1           1           1           1           1           1           1           1
i15                       1           1           1           1
i17                       1           1           1           1           1           1           1           1
i18                                                           1           1           1           1           1
i20                                                                                                           1

  +         h09         h10         h11         h12         h13         h14         h15         h16         h17

i3                                    1           1
i5            1           1           1           1
i6            1           1           1           1
i9            1
i10                       1           1           1           1
i12                                               1           1           1           1           1           1
i14                                                                                                           1
i16                                                           1           1           1           1
i18           1           1           1           1
i19                                                                       1           1           1           1
i20           1           1           1           1           1

  +         h18         h19         h20         h21         h22         h23

i2                        1           1           1           1           1
i8                        1           1           1           1           1
i11                                                           1           1
i12           1
i13                                                           1           1
i14           1           1           1           1           1           1
i19           1           1           1           1

(Note: zeros are not printed)

Now we can formulate a MIP model:

When we solve this with a standard MIP solver we get the following solution:

----     29 VARIABLE x.L  selected items

i9  1,    i10 1,    i13 1,    i19 1


----     29 VARIABLE cost.L                =          196  total cost

Note that is is quite possible the problem is infeasible: we cannot cover each hour with exactly one item. For practical applications, it may be beneficial to protect ourselves against this. E.g. by allowing to insert very expensive "emergency items" into the solution (say we have 24 of them, one for each hour, at a very high cost). This will always deliver a solution, and you can see which time slots we have problems with.