Scheduling Examples

Bus Scheduling

Original problem from here.

A bus company is scheduling drivers for its buses. The number of drivers needed varies from hour to hour because of customer demand (8 a.m. will have more demand than 3 a.m.). Below is a schedule for the minimum number of buses needed for each time period.

Shift	Min. Buses
0 - 4	4
4 - 8	8
8 - 12	10
12 - 16	7
16 - 20	12
20 - 0	4

The problem is to determine how many drivers to schedule at each starting time to cover the requirements for buses. Drivers work eight hour shifts that start at times: 0, 4, 8, 12, 16 or 20. For example, a driver starting at time 0 can drive a bus from time 0 to 8. A driver scheduled to start at time 20 works for the final four hours of the day and the first four hours of the next day. The goal is to minimize the number of drivers used. Note that although a driver can be hired for an eight hour period, there is no requirement that he drive a bus for the entire period. He might be idle for a four hour interval within the period.

Solution

   var model = {
      optimize: "ppl",
      opType: "min",
      constraints: {
          d0: {min: 4},
          d4: {min: 8},
          d8: {min: 10},
          d12: {min: 7},
          d16: {min: 12},
          d20: {min: 4}
      },
      variables: {
          shft_0: {d0: 1, d4: 1, ppl: 1},
          shft_4: {d4: 1, d8: 1, ppl: 1},
          shft_8: {d8: 1, d12: 1, ppl: 1},
          shft_12: {d12: 1, d16: 1, ppl: 1},
          shft_16: {d16: 1, d20: 1, ppl: 1},
          shft_20: {d20: 1, d0: 1, ppl: 1}
      }
  };

  solver.Solve(model);
/*
    feasible: true
    result: 26
    shft_0: 4
    shft_4: 10
    shft_12: 8
    shft_16: 4
*/