Question

Please formulate and solve the following problem.

Problem 2: Consider a taxi company scheduling drivers for its taxis. The requirement for taxis varies from hour to hour because of customer demand as shown in the figure. Time 0 on the figure represents midnight, and times are shown with a 24 hour clock starting at midnight. For example, four taxis must run from midnight to 4 a.m., while eight taxis must run from 4 a.m. until 8 a.m. We assume that the taxi requirements are the same every day.

The problem is to determine how many drivers to schedule at each starting time to cover the requirements for taxis. 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 taxi 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 taxi for the entire period. He might be idle for a four hour interval within the period.

Hour Start	0	4	8	12	16	20
Taxi Demand	5	8	11	7	14	6

Answer 1

Following is the algorithm to determine the number of drivers that are required at each time. This is stored in driversRequired.

array taxiDemand = size 24 // given as input

array CurrentDrivers = size 24 with default values to 0

array driversRequired = size 24 with default values to 0

iterate index from 0 to 24 with a gap of 4:
int taxiRequired = taxiDemand[index];
int delta = taxiRequired - CurrentDrivers[index];
// if delta > 0, we need to add these many drivers that start from this time for eight hours.
if delta > 0
currentDrivers[index] += delta;
currentDrivers[index + 4] += delta;
driversRequired[index] = delta;

Since the day has to start from morning, we are assuming that there is no previous night driver could be reused in the morning (0-4). This can be done for next days and can save on the drivers more. The methodology would be similar in that case as well. There would few drivers that would be available at CurrentDrivers[0].