A bus company needs to create a schedule for its drivers. The number of drivers that are needed varies during the day and is shown in the table below. Time 00:00 and 24:00 on the left and right represent midnight at the beginning and the end of the day. This is the same demand for every day.

Time slot	00.00 04.00	04.00 08.00	08.00 12.00	12.00 16.00	16.00 20.00	20.00 24.00
# of buses	4	8	10	7	12	4

The drivers always work in shifts that take eight hours. The shifts start at 00:00, 04:00, 08:00, 12:00, 16:00 and 20:00 and end 8 hours later. Notice that a driver that starts at 20:00 drives until 04:00. Although drivers are always hired for a shift of eight hours, it is not necessary that the driver is driving a bus during the full eight hours. Due to the uneven demand, the driver might only drive during four hours of the eight. The company needs to decide for every possible starting time how many bus drivers start their shift then.

As an example, an easy solution to this problem would be to hire 8 drivers starting at 00:00, 10 drivers starting at 08:00 and 12 drivers starting at 16:00. This solution requires 30 drivers. The company wants to find a schedule that minimizes the number of required drivers. Of course, in a general solution, shifts can also start at all other possible start times.

The company will solve this using integer linear programming. They start as follows.

The set i = 1, 2, 3, 4, 5, 6 represents the times 00:00, 04:00, 08:00, 12:00, 16:00 and 20:00.

The parameter d_i represents the required number of bus drivers in the four-hour time window starting at time i. For example, d₂ = 8 in the table above.

a. Write down the ILP for the bus company to minimize the number of bus drivers that are needed to cover the demand. Use the notation for the set above. You are encouraged, but not required, to use the notation for the parameter. Clearly define any new notation you introduce for e.g. your decision variables.

A new manager enters the company. She wants to introduce a new schedule in which every bus driver works either a shift of only four hours, or a full shift of eight hours. From now on, at every time i, a schedule needs to specify the number of bus drivers that start an eight-hour shift and the number of drivers that start a four-hour shift.

The labour costs for bus drivers also vary per shift due to the collective labour agreement. The following table gives the hourly labour costs for every bus driver that drives during the four hours following that time. For example, the bus company needs to pay a bus driver with a shift from 12:00 to 20:00 15 per hour for the first four hours, and 16 per hour for the last four hours.

Time slot	00.00 04.00	04.00 08.00	08.00 12.00	12.00 16.00	16.00 20.00	20.00 24.00
Hourly labour costs	20	18	15	15	16	18

Instead of minimizing the required number of bus drivers, the company decides to minimize the total labour costs that they need to pay its drivers.

b. Write down the ILP for the bus company to minimize the total labour costs. You are encouraged, but not required, to use the notation that is introduced above. Clearly define any new notation you introduce for e.g. your decision variables.

c. Due to regulations, at most 25% of employees can work only 4 hours a day and at least 75% of employees need to have an eight-hour shift. Moreover, it is only allowed to give a bus driver a four-hour shift from 00:00 to 04:00 if there are at least 3 bus drivers with an eight-hour shift from 20:00 to 04:00. How does your ILP from question b change if you incorporate these two new rules?