# Scheduling Algorithms

Organizations use scheduling systems to optimize production. A mathematical scheduling approach is very useful for the right production applications. Lean systems use pull scheduling systems coordinated by visual or electronic controls. To demonstrate the importance of scheduling rules to reduce lead time, Figure 5.16 shows two scheduling models

**FIGURE 5.16**

How scheduling rules impact material flow. FIFO = first in, first out.

that differ only with respect to rules. The first model uses a first come, first served scheduling rule (FIFO), whereas the second uses a minimum processing time rule. The calculations show it is easy to see that, for this example, the minimum processing time scheduling rule reduces both the number of late jobs as well as the lead time for all ten jobs processed through the system (i.e., 156 versus 115 days). The underlying concept is that a transfer batch model reduces lead time over a batch model. In this simple example, the scheduling rules had a large impact on a system’s lead time. Prioritization rules have a significant impact on a process efficiency.

The second scheduling algorithm is shown in Figure 5.17. This is an assignment model in which *n* jobs are assigned to exactly *n* work cells based on the historical processing time or cost for every combination of job and work cell. The example models an *n x n* use case. It should be noted that in more complex situations in which there are *n* jobs and *m* work cells, the number of alternative schedules rapidly increases according to the formula («!)'". In these more complex analyses, a solution requires an analysis using simulation methods. There are three steps in using the assignment algorithm. The first step makes row calculations in which the smallest number (i.e., time or cost) in a row is removed from all other numbers in the same row. The second step requires the same calculations to be made column-wise by removing the smallest number in every column from other numbers in the same column to create a reduced matrix. In the third step, a test is made to see if exactly *n* lines can cover all the Os. In the current example, exactly *n* lines cover all the Os, showing an optimal assignment of jobs to work cells. This optimum assignment recommends assigning Job 1 to Work Cell 1, Job 2 to Work Cell 3, Job 3 to Work Cell 4, and Job 4 to Work Cell 2. The total processing cost equals $60 + $35 + $45 + $25 = $165, which is the minimum for this example.

In Figure 5.18, a more sophisticated algorithm is used to schedule at least two days off per week per employee. In this algorithm, starting with Worker 1, the days requiring the smallest number of employees (i.e., Wednesday and Friday) are scheduled as days off for Worker 1. In the second iteration, the schedule of Worker 2 is determined by first removing one day from the original daily schedule except for the days off taken by Worker 1. This is because Worker 1 will work these days (i.e., Monday, Tuesday, Thursday, Friday, and Sunday). These five days now require one

**FIGURE 5.17**

Assignment algorithm (n_{jobs} to n_{workcells}).

**FIGURE 5.18**

Scheduling workers.

less person to meet their schedule. The algorithm continues until each day has been assigned the required number of workers, with each worker having at least two days off from work. In summary, this algorithm demonstrates an efficient method to schedule resources.

Figure 5.19 shows an integer linear programming model applied to a scheduling model. The objective is to satisfy all required schedules with a minimum number of agents per shift and at minimum cost. In this example, the objective function is to minimize monthly salary cost, given each shift has a constraint relative to the minimum number of agents assigned to it. Notice that the schedule is classified into 4-hour time intervals spaced over six periods. This schedule could also have been classified into hours. Because agents work an 8-hour shift, there are multiple shifts working in parallel in any four-hour period. As an example, Period 1 starts at 8 AM and ends at 4 PM. Between 8 AM and 12 PM, 20 agents are needed to answer customer calls. However, during the period of 12 PM to 4 PM, 30 agents are needed. This implies that 10 additional agents must be added between 12 PM and 4 PM. The constraint on the staffing schedule is that an agent cannot work more than 8 hours in a 24-hour day. This means four shifts of workers must be staffed according to the solution provided at the bottom of Figure 5.19. Shift 1 should be staffed using

**FIGURE 5.19**

Linear programming model applied to scheduling.

20 agents, Shift 2 using 10 agents, Shift 3 using 30 agents, and Shift 4 using 10 agents. This optimum solution will require 140 agents for a total monthly salary of $165,000. This is the minimum cost solution obtained using the LP algorithm. LP algorithms provide extreme flexibly to model different scheduling systems and constraints.

Over the past several years, advanced software has been developed to increase the efficiency of a scheduling process. These are based on LP or simulation algorithms with user-friendly interfaces and easy-to-under- stand decision-making tools that optimize resources to satisfy demand at minimum cost based on capacity and other user-defined system constraints. In fact, sophisticated scheduling software routinely provides detailed staffing schedules based on worker skill levels, function, location, shift, pay rate, restrictions on schedule, and other constraints.