Scheduling Elevators |
TASK. In some buildings, all of the elevators can travel to all of the floors, while in others the elevators are restricted to stopping only on certain floors. What is the advantage of having elevators that travel only to certain floors? When is this worth instituting?
COMMENTARY. Scheduling elevators is a common example of an optimization problem that has applications in all aspects of business and industry. Optimal scheduling in general not only can save time and money, but it can contribute to safety (e.g., in the airline industry). The elevator problem further illustrates an important feature of many economic and political arguments--the dilemma of trying simultaneously to optimize several different needs.
Politicians often promise policies that will be the least expensive, save the most lives, and be best for the environment. Think of flood control or occupational safety rules, for example. When we are lucky, we can perhaps find a strategy of least cost, a strategy that saves the most lives, or a strategy that damages the environment least. But these might not be the same strategies: generally one cannot simultaneously satisfy two or more independent optimization conditions. This is an important message for students to learn, in order to become better educated and more critical consumers and citizens.
In the elevator problem, customer satisfaction can be emphasized by minimizing the average elevator time (waiting plus riding) for employees in an office building. Minimizing wait-time during rush hours means delivering many people quickly, which might be accomplished by filling the elevators and making few stops. During off-peak hours, however, minimizing wait-time means maximizing the availability of the elevators. There is no reason to believe that these two goals will yield the same strategy. Finding the best strategy for each is a mathematical problem; choosing one of the two strategies or a compromise strategy is a management decision, not a mathematical deduction.
This example serves to introduce a complex topic whose analysis is well within the range of high school students. Though the calculations require little more than arithmetic, the task puts a premium on the creation of reasonable alternative strategies. Students should recognize that some configurations (e.g., all but one elevator going to the top floor and the one going to all the others) do not merit consideration, while others are plausible. A systematic evaluation of all possible configurations is usually required to find the optimal solution. Such a systematic search of the possible solution space is important in many modeling situations where a formal optimal strategy is not known. Creating and evaluating reasonable strategies for the elevators is quite appropriate for high school student mathematics and lends itself well to thoughtful group effort. How do you invent new strategies? How do you know that you have considered all plausible strategies? These are mathematical questions, and they are especially amenable to group discussion.
Students should be able to use the techniques first developed in solving a simple case with only a few stories and a few elevators to address more realistic situations (e.g., 50 stories, five elevators). Using the results of a similar but simpler problem to model a more complicated problem is an important way to reason in mathematics. Students need to determine what data and variables are relevant. Start by establishing the kind of building--a hotel, an office building, an apartment building? How many people are on the different floors? What are their normal destinations (e.g., primarily the ground floor or, perhaps, a roof-top restaurant). What happens during rush hours?
To be successful at the elevator task, students must first develop a mathematical model of the problem. The model might be a graphical representation for each elevator, with time on the horizontal axis and the floors represented on the vertical axis, or a tabular representation indicating the time spent on each floor. Students must identify the pertinent variables and make simplifying assumptions about which of the possible floors an elevator will visit.
MATHEMATICAL ANALYSIS. This section works through some of the details in a particularly simple case. Consider an office building with six occupied floors, employing 240 people, and a ground floor that is not used for business. Suppose there are three elevators, each of which can hold 10 people. Further suppose that each elevator takes approximately 25 seconds to fill on the ground floor, then takes 5 seconds to move between floors and 15 seconds to open and close at each floor on which it stops.
Scenario one. What happens in the morning when everyone arrives for work? Assume that everyone arrives at approximately the same time and enters the elevators on the ground floor. If all elevators go to all floors and if the 240 people are evenly divided among all three elevators, each elevator will have to make 8 trips of 10 people each.
When considering a single trip of one elevator, assume for simplicity that 10 people get on the elevator at the ground floor and that it stops at each floor on the way up, because there may be an occupant heading to each floor. Adding 5 seconds to move to each floor and 15 seconds to stop yields 20 seconds for each of the six floors. On the way down, since no one is being picked up or let off, the elevator does not stop, taking 5 seconds for each of six floors for a total of 30 seconds. This round-trip is represented in Table 1.
Table 1:
|
||||||||||||||||||||||
|
||||||||||||||||||||||
|
|
||||||||||||||||||||||
Since each elevator makes 8 trips, the total time will be 1,400 seconds or 23 minutes, 20 seconds.
Scenario two. Now suppose that one elevator serves floors 13 and, because of the longer trip, two elevators are assigned to floors 46. The elevators serving the top floors will save 15 seconds for each of floors 13 by not stopping. The elevator serving the bottom floors will save 20 seconds for each of the top floors and will save time on the return trip as well. The times for these trips are shown in Table 2.
Table 2:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Assuming the employees are evenly distributed among the floors (40 people per floor), elevator A will transport 120 people, requiring 12 trips, and elevators B and C will transport 120 people, requiring 6 trips each. These trips will take 1200 seconds (20 minutes) for elevator A and 780 seconds (13 minutes) for elevators B and C, resulting in a small time savings (about 3 minutes) over the first scenario. Because elevators B and C are finished so much sooner than elevator A, there is likely a more efficient solution.
Scenario three. The two round-trip times in Table 2 do not differ by much because the elevators move quickly between floors but stop at floors relatively slowly. This observation suggests that a more efficient arrangement might be to assign each elevator to a pair of floors. The times for such a scenario are listed in Table 3.
Table 3:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Again assuming 40 employees per floor, each elevator will deliver 80 people, requiring 8 trips, taking at most a total of 920 seconds. Thus this assignment of elevators results in a time savings of almost 35% when compared with the 1400 seconds it would take to deliver all employees via unassigned elevators.
Perhaps this is the optimal solution. If so, then the above analysis of this simple case suggests two hypotheses:
1. The optimal solution assigns each floor to a single elevator.
2. If the time for stopping is sufficiently larger than the time for moving between floors, each elevator should serve the same number of floors.
Mathematically, one could try to show that this solution is optimal by trying all possible elevator assignments or by carefully reasoning, perhaps by showing that the above hypotheses are correct. Practically, however, it doesn't matter because this solution considers only the morning rush hour and ignores periods of low use.
The assignment is clearly not optimal during periods of low use, and much of the inefficiency is related to the first hypothesis for rush hour optimization: that each floor is served by a single elevator. With this condition, if an employee on floor 6 arrives at the ground floor just after elevator C has departed, for example, she or he will have to wait nearly two minutes for elevator C to return, even if elevators A and B are idle. There are other inefficiencies that are not considered by focusing on the rush hour. Because each floor is served by a single elevator, an employee who wishes to travel from floor 3 to floor 6, for example, must go via the ground floor and switch elevators. Most employees would prefer more flexibility than a single elevator serving each floor.
At times when the elevators are not all busy, unassigned elevators will provide the quickest response and the greatest flexibility. Because this optimal solution conflicts with the optimal rush hour solution, some compromise is necessary. In this simple case, perhaps elevator A could serve all floors, elevator B could serve floors 1-3, and elevator C could serve floors 4-6.
The second hypothesis, above, deserves some further thought. The efficiency of the rush hour solution Table 3 is due in part to the even division of employees among the floors. If employees were unevenly distributed with, say, 120 of the 240 people working on the top two floors, then elevator C would need to make 12 trips, taking a total of 1380 seconds, resulting in almost no benefit over unassigned elevators. Thus, an efficient solution in an actual building must take into account the distribution of the employees among the floors.
Because the stopping time on each floor is three times as large as the traveling time between floors (15 seconds versus 5 seconds), this solution effectively ignores the traveling time by assigning the same number of employees to each elevator. For taller buildings, the traveling time will become more significant. In those cases fewer employees should be assigned to the elevators that serve the upper floors than are assigned to the elevators that serve the lower floors.
EXTENSIONS. The problem can be made more challenging by altering the number of elevators, the number of floors, and the number of individuals working on each floor. The rate of movement of elevators can be determined by observing buildings in the local area. Some elevators move more quickly than others. Entrance and exit times could also be measured by students collecting data on local elevators. In a similar manner, the number of workers, elevators, and floors could be taken from local contexts.
A related question is, where should the elevators go when not in use? Is it best for them to return to the ground floor? Should they remain where they were last sent? Should they distribute themselves evenly among the floors? Or should they go to floors of anticipated heavy traffic? The answers will depend on the nature of the building and the time of day. Without analysis, it will not be at all clear which strategy is best under specific conditions. In some buildings, the elevators are controlled by computer programs that "learn" and then anticipate the traffic patterns in the building.
A different example that students can easily explore in detail is the problem of situating a fire station or an emergency room in a city. Here the key issue concerns travel times to the region being served, with conflicting optimization goals: average time vs. maximum time. A location that minimizes the maximum time of response may not produce the least average time of response. Commuters often face similar choices in selecting routes to work. They may want to minimize the average time, the maximum time, or perhaps the variance, so that their departure and arrival times are more predictable.
Most of the optimization conditions discussed so far have been expressed in units of time. Sometimes, however, two optimization conditions yield strategies whose outcomes are expressed in different (and sometimes incompatible) units of measurement. In many public policy issues (e.g., health insurance) the units are lives and money. For environmental issues, sometimes the units themselves are difficult to identify (e.g., quality of life).
When one of the units is money, it is easy to find expensive strategies but impossible to find ones that have virtually no cost. In some situations, such as airline safety, which balances lives versus dollars, there is no strategy that minimize lives lost (since additional dollars always produce slight increases in safety), and the strategy that minimizes dollars will be at $0. Clearly some compromise is necessary. Working with models of different solutions can help students understand the consequences of some of the compromises.
 |
 |
 |
