# Determining optimal employee schedules through use of the first period principle.

Employee scheduling for manufacturing operations is typically
concerned with devising effective ways of dealing with seasonal (annual)
variations in demand so that a relatively stable workforce will be able
to satisfy the expected demands without relying on excessive goods
inventories. In scheduling employees for service operations, one is more
commonly concerned with daily, hourly or finer variations in demand.

In general, one must find ways of balancing staff idle time (which represents a loss since it cannot be inventoried for later use) and customer waiting time. This is often done by establishing a service standard and determining the staffing required for each of the various levels of demand expected. Many services must be provided continuously, 24 hours per day, seven days per week. Since both people and organizations operate on daily and weekly cycles, demands for services -- and, thus staffing requirements -- often vary in daily and weekly cycles. Demand cycles are usually predictable based on analysis of past experience. Employee work schedules are typically based on eight-hour work tours on each of five consecutive days per week. Thus, many service organizations are faced with the problem of developing daily tour schedules that minimize the number of employees scheduled to meet a weekly cycle of hourly requirements.

Optimal scheduling methods can be described for the following cases:

* Non-cyclic case -- scheduling work tours of p(1) consecutive hours each to meet a continuous arbitrary stream of hourly requirements;

* Cyclic case -- scheduling tours of p(2) consecutive hours per employee over a repeating cycle of requirements. The same basic methodology for p of n cyclic scheduling applies to the cyclic days-off case -- scheduling p(3) consecutive work days per cycle of seven days; and

* Cyclic case with restricted starting (or ending) times -- scheduling work tours of p(4) consecutive hours per employee over a repeating cycle of 24 hours or 168 hours of requirements.

The discussion of the third of these TABULAR DATA OMITTED cases, i.e., tours with restricted starting times, will explain how a minor modification in the interpretation of the first period principle extends its applicability so that the revised procedure provides optimal solutions to this more general case.

Although the methodology will be described and illustrated using eight-hour tours (i.e., p(1) = p(2) = 8) and a 168-hour cycle length and for five days work per cycle of seven, the procedures described will yield optimal solutions in the general scheduling problem of p consecutive work periods per cycle of n.

Consecutive period scheduling

Guha developed a condition sufficient for optimal scheduling of p consecutive periods per worker in each cycle of n periods. Using this as a base, Browne, Propp and Tibrewala provided a solution to the non-cyclic problem based on the first hour principle, whereby one assigns the number of employees to start work at any hour as exactly the number of workers needed to meet any portion of hour requirements that has not been satisfied by previously assigned workers and defined conditions sufficient for an optimal solution. Browne and Tibrewala proposed a method based on Guha's condition (for every period either the assignment or the slack equals zero) that gave optimal solutions for the general p of n problem in most cases. Propp provided a method of obtaining optimal solutions, not necessarily integer, to the general p of n consecutive work periods problem. A paper by Browne expanded on and illustrated Propp's method and made the results more readily accessible. Bartholdi, Orlin and Ratliff showed how to extend the results for a class of non-integer solutions to the integer case and this was related to the scheduling application by Browne and Propp.

Non-cyclic case

Given an arbitrary stream of requirements R(1), R(2),...R(N) per period, let X(1), X(2),...,X(N) be the number of employees beginning work in each period and working for that period and the following (p-1) periods. We wish to find a set of X(i) such that the sum of the X(i) is minimized subject to the condition that all requirements are met. The optimal solution set for X(i) can be obtained by applying the first period principle: assign X(i) so as to exactly meet the requirements remaining after the proceeding assignments X(1), X(2),...,X(i-1). Thus X(1) = R(1) and each:

|Mathematical Expression Omitted~

Each X(i) assigned in this way does, by definition, meet requirement R(i). Further it is a minimal assignment because any reduction to an assignment X(i) will lead to a non-feasible assignment.

Cyclic case

Next consider a cyclic case, i.e., one in which a set of requirements per period R(1), R(2),....,R(n) is repeated over and over and the problem is to find a single set of X(1), X(2),...,X(n), the number of employees starting per period with each working for p consecutive periods (p is less than n) so that requirements are met and the number of employees is minimized. If we conceive the successive cycles as a single stream of periods and make each assignment by the first period principle, the solution obtained will be optimal for any finite stream of requirements (non-cyclic case) but will not necessarily be optimal for the cyclic case since the initial set of (p-1) assignments do not take account of the reductions in requirements due to employees assigned toward the end of the cycle.

If we continue to make assignments, however, as in the non-cyclic case, the pattern of assignments per period must eventually repeat those of a previous cycle of n. Since p is finite and all of X(i) are finite, there are a limited number of different combinations of assignments that can be made. Note, for example, that no X(i) can ever exceed R(i). Any repeating cycle of assignments based on the first period principle will be optimal for the same reason as in the non-cyclic case; it is feasible and any lesser individual assignment will not be feasible. If the period of the repetition contains r cycles of n periods each, note that the average assignment X(i) over the r cycles must also be both feasible and optimal. Since requirements are met in total over the r periods, the average assignment must also satisfy the average requirement R(i) per period. Of course, the average assignments X(i) may not be integers.

Restricted starting (or ending) times

Often certain starting times are not permitted. For example, 1 a.m. to 5 a.m. starting TABULAR DATA OMITTED times might not be permitted. Thus any assignment in the last period preceding the restricted starting times must also satisfy the requirements for these later restricted hours. If we take this into account in applying the first period principle to the hours preceding restrictions, our assignments will again be feasible and optimal (for the same reason as for the unrestricted hours case), a repeating cycle will occur (since requirements are still finite) and the round off algorithm will provide the optimal integer solution (since periods worked are still consecutive). Note also that restrictions on ending times are easily translated into equivalent restrictions on starting times. If, for example, 1 a.m. to 5 a.m. ending times are not permissible and eight consecutive hours are worked, then starting times of 5 p.m. to 9 p.m. would not be permitted.

The comparison of unrestricted and restricted solutions are shown in Figure 1. Given the set of 24 cyclic requirements in column 2, columns 3 and 4 represent the assignments by the first period principle and column 4 is a repeating cycle of 24 assignments. Thus, the optimal solution requires 20 employees with the starting times indicated in column 4.

If the starting times marked R are not permitted, then the assignment at 4 to 5 p.m. must be altered from five to nine employees in the initial set of assignments. The resulting set of assignments in column 5 represents a repeating cycle and this provides an optimal solution for the restricted case - requiring 21 employees with the starting times indicated in column 5.

The use of restricted starting times to create "windows" defining allowable shift starting times is an important practical application of this methodology. The use of starting time windows to define shifts in shown in Figure 2. It is understood that all starting times except those denoted by shift 1, shift 2 and shift 3 are restricted, (i.e. only times defined for shift 1, shift 2 and shift 3 are allowed). For purposes of illustration these allow some starting times that were restricted in Figure 1. For the Figure 2 starting times, assignment 2 repeats and provides a solution requiring only 20 tours.

For larger (e.g. 168 hours of requirements) and more complex (e.g. where repeating cycles do not occur as quickly and yield non-integer solutions required round-off to the optimal solution), the reader is referred to Nanda and Browne. This text contains details and examples of the round-off procedures, more complex applications including days off, tours and integrated work weeks scheduling (both tours and days off) as well as a computer diskette (employee scheduling programs) that can be used to avoid the burden of tedious or lengthy calculations.

Jim Browne is on the adjunct faculty staffs of the Fordham and New York University Graduate Schools of Business. He is the author of Management and Analysis of Service Operations and co-author of Introduction to Employee Scheduling.

For further reading

Baker K., "Scheduling Full-Time and Part-Time Staff to Meet Cyclical Requirements," Operations Research Quarterly, March 1975.

Baker K., T. Crabill and M. Magazine, "An Optimal Procedure for Allocating Manpower with Cyclic Requirements," IIE Transactions, June 1973.

Bartholdi J., J. Orlin and H. Ratliff, "Cyclic Scheduling Via Integer Programs with Circular Ones," Operations Research, September 1980.

Bodin L., "Towards a General Model for Manpower Scheduling - Parts I and Il," Journal of Urban Analysis, Vol. 1, no. 2.

Browne J., "Simplified Scheduling of Routine Work Hours and Days-Off," Industrial Engineering, December 1979.

Browne, J. and R. Nanda, "Scheduling Efficiency of the Four-Day Week at Transportation Facilities," Institute of Transportation Engineers Proceedings, August 1987.

Browne J. and J. Propp, "Supplement to Scheduling Routine Work Hours," Industrial Engineering, July 1980.

Browne J., J. Propp and R. Tibrewala, "Conditions for Optimal Scheduling of Consecutive Work Periods," Paper Presented at TIMS-ORSA National Meeting, New York, May 1978.

Browne J. and R. Tibrewala, "A Simple Method for Obtaining Cyclic Employee Schedules" in L. Ritzman, et al, eds., Dissaggregation Problems in Manufacturing and Service Organizations, Boston: Martinus Nijhoff, 1979.

Buffa E., M. Cosgrove and B. Luce, "An Integrated Work Shift Scheduling System," Decision Sciences, October 1976.

Guha D., "An Optimal Procedure for Allocating Manpower with Cycle Requirements: General Case," ORSA-TIMS Conference, San Juan, October 1974.

Nanda R. and J. Browne, Introduction to Employee Scheduling, New York: Van Nostrand Reinhold, 1992.

Propp J., "A Greedy Solution for Linear Programs With Circular Ones," IBM Corporation Interim Report, 1978.

Segal M., "The Operator Scheduling Problem: A Network Flow Approach," Operations Research, July 1974.

In general, one must find ways of balancing staff idle time (which represents a loss since it cannot be inventoried for later use) and customer waiting time. This is often done by establishing a service standard and determining the staffing required for each of the various levels of demand expected. Many services must be provided continuously, 24 hours per day, seven days per week. Since both people and organizations operate on daily and weekly cycles, demands for services -- and, thus staffing requirements -- often vary in daily and weekly cycles. Demand cycles are usually predictable based on analysis of past experience. Employee work schedules are typically based on eight-hour work tours on each of five consecutive days per week. Thus, many service organizations are faced with the problem of developing daily tour schedules that minimize the number of employees scheduled to meet a weekly cycle of hourly requirements.

Optimal scheduling methods can be described for the following cases:

* Non-cyclic case -- scheduling work tours of p(1) consecutive hours each to meet a continuous arbitrary stream of hourly requirements;

* Cyclic case -- scheduling tours of p(2) consecutive hours per employee over a repeating cycle of requirements. The same basic methodology for p of n cyclic scheduling applies to the cyclic days-off case -- scheduling p(3) consecutive work days per cycle of seven days; and

* Cyclic case with restricted starting (or ending) times -- scheduling work tours of p(4) consecutive hours per employee over a repeating cycle of 24 hours or 168 hours of requirements.

The discussion of the third of these TABULAR DATA OMITTED cases, i.e., tours with restricted starting times, will explain how a minor modification in the interpretation of the first period principle extends its applicability so that the revised procedure provides optimal solutions to this more general case.

Although the methodology will be described and illustrated using eight-hour tours (i.e., p(1) = p(2) = 8) and a 168-hour cycle length and for five days work per cycle of seven, the procedures described will yield optimal solutions in the general scheduling problem of p consecutive work periods per cycle of n.

Consecutive period scheduling

Guha developed a condition sufficient for optimal scheduling of p consecutive periods per worker in each cycle of n periods. Using this as a base, Browne, Propp and Tibrewala provided a solution to the non-cyclic problem based on the first hour principle, whereby one assigns the number of employees to start work at any hour as exactly the number of workers needed to meet any portion of hour requirements that has not been satisfied by previously assigned workers and defined conditions sufficient for an optimal solution. Browne and Tibrewala proposed a method based on Guha's condition (for every period either the assignment or the slack equals zero) that gave optimal solutions for the general p of n problem in most cases. Propp provided a method of obtaining optimal solutions, not necessarily integer, to the general p of n consecutive work periods problem. A paper by Browne expanded on and illustrated Propp's method and made the results more readily accessible. Bartholdi, Orlin and Ratliff showed how to extend the results for a class of non-integer solutions to the integer case and this was related to the scheduling application by Browne and Propp.

Non-cyclic case

Given an arbitrary stream of requirements R(1), R(2),...R(N) per period, let X(1), X(2),...,X(N) be the number of employees beginning work in each period and working for that period and the following (p-1) periods. We wish to find a set of X(i) such that the sum of the X(i) is minimized subject to the condition that all requirements are met. The optimal solution set for X(i) can be obtained by applying the first period principle: assign X(i) so as to exactly meet the requirements remaining after the proceeding assignments X(1), X(2),...,X(i-1). Thus X(1) = R(1) and each:

|Mathematical Expression Omitted~

Each X(i) assigned in this way does, by definition, meet requirement R(i). Further it is a minimal assignment because any reduction to an assignment X(i) will lead to a non-feasible assignment.

Cyclic case

Next consider a cyclic case, i.e., one in which a set of requirements per period R(1), R(2),....,R(n) is repeated over and over and the problem is to find a single set of X(1), X(2),...,X(n), the number of employees starting per period with each working for p consecutive periods (p is less than n) so that requirements are met and the number of employees is minimized. If we conceive the successive cycles as a single stream of periods and make each assignment by the first period principle, the solution obtained will be optimal for any finite stream of requirements (non-cyclic case) but will not necessarily be optimal for the cyclic case since the initial set of (p-1) assignments do not take account of the reductions in requirements due to employees assigned toward the end of the cycle.

If we continue to make assignments, however, as in the non-cyclic case, the pattern of assignments per period must eventually repeat those of a previous cycle of n. Since p is finite and all of X(i) are finite, there are a limited number of different combinations of assignments that can be made. Note, for example, that no X(i) can ever exceed R(i). Any repeating cycle of assignments based on the first period principle will be optimal for the same reason as in the non-cyclic case; it is feasible and any lesser individual assignment will not be feasible. If the period of the repetition contains r cycles of n periods each, note that the average assignment X(i) over the r cycles must also be both feasible and optimal. Since requirements are met in total over the r periods, the average assignment must also satisfy the average requirement R(i) per period. Of course, the average assignments X(i) may not be integers.

Restricted starting (or ending) times

Often certain starting times are not permitted. For example, 1 a.m. to 5 a.m. starting TABULAR DATA OMITTED times might not be permitted. Thus any assignment in the last period preceding the restricted starting times must also satisfy the requirements for these later restricted hours. If we take this into account in applying the first period principle to the hours preceding restrictions, our assignments will again be feasible and optimal (for the same reason as for the unrestricted hours case), a repeating cycle will occur (since requirements are still finite) and the round off algorithm will provide the optimal integer solution (since periods worked are still consecutive). Note also that restrictions on ending times are easily translated into equivalent restrictions on starting times. If, for example, 1 a.m. to 5 a.m. ending times are not permissible and eight consecutive hours are worked, then starting times of 5 p.m. to 9 p.m. would not be permitted.

The comparison of unrestricted and restricted solutions are shown in Figure 1. Given the set of 24 cyclic requirements in column 2, columns 3 and 4 represent the assignments by the first period principle and column 4 is a repeating cycle of 24 assignments. Thus, the optimal solution requires 20 employees with the starting times indicated in column 4.

If the starting times marked R are not permitted, then the assignment at 4 to 5 p.m. must be altered from five to nine employees in the initial set of assignments. The resulting set of assignments in column 5 represents a repeating cycle and this provides an optimal solution for the restricted case - requiring 21 employees with the starting times indicated in column 5.

The use of restricted starting times to create "windows" defining allowable shift starting times is an important practical application of this methodology. The use of starting time windows to define shifts in shown in Figure 2. It is understood that all starting times except those denoted by shift 1, shift 2 and shift 3 are restricted, (i.e. only times defined for shift 1, shift 2 and shift 3 are allowed). For purposes of illustration these allow some starting times that were restricted in Figure 1. For the Figure 2 starting times, assignment 2 repeats and provides a solution requiring only 20 tours.

For larger (e.g. 168 hours of requirements) and more complex (e.g. where repeating cycles do not occur as quickly and yield non-integer solutions required round-off to the optimal solution), the reader is referred to Nanda and Browne. This text contains details and examples of the round-off procedures, more complex applications including days off, tours and integrated work weeks scheduling (both tours and days off) as well as a computer diskette (employee scheduling programs) that can be used to avoid the burden of tedious or lengthy calculations.

Jim Browne is on the adjunct faculty staffs of the Fordham and New York University Graduate Schools of Business. He is the author of Management and Analysis of Service Operations and co-author of Introduction to Employee Scheduling.

For further reading

Baker K., "Scheduling Full-Time and Part-Time Staff to Meet Cyclical Requirements," Operations Research Quarterly, March 1975.

Baker K., T. Crabill and M. Magazine, "An Optimal Procedure for Allocating Manpower with Cyclic Requirements," IIE Transactions, June 1973.

Bartholdi J., J. Orlin and H. Ratliff, "Cyclic Scheduling Via Integer Programs with Circular Ones," Operations Research, September 1980.

Bodin L., "Towards a General Model for Manpower Scheduling - Parts I and Il," Journal of Urban Analysis, Vol. 1, no. 2.

Browne J., "Simplified Scheduling of Routine Work Hours and Days-Off," Industrial Engineering, December 1979.

Browne, J. and R. Nanda, "Scheduling Efficiency of the Four-Day Week at Transportation Facilities," Institute of Transportation Engineers Proceedings, August 1987.

Browne J. and J. Propp, "Supplement to Scheduling Routine Work Hours," Industrial Engineering, July 1980.

Browne J., J. Propp and R. Tibrewala, "Conditions for Optimal Scheduling of Consecutive Work Periods," Paper Presented at TIMS-ORSA National Meeting, New York, May 1978.

Browne J. and R. Tibrewala, "A Simple Method for Obtaining Cyclic Employee Schedules" in L. Ritzman, et al, eds., Dissaggregation Problems in Manufacturing and Service Organizations, Boston: Martinus Nijhoff, 1979.

Buffa E., M. Cosgrove and B. Luce, "An Integrated Work Shift Scheduling System," Decision Sciences, October 1976.

Guha D., "An Optimal Procedure for Allocating Manpower with Cycle Requirements: General Case," ORSA-TIMS Conference, San Juan, October 1974.

Nanda R. and J. Browne, Introduction to Employee Scheduling, New York: Van Nostrand Reinhold, 1992.

Propp J., "A Greedy Solution for Linear Programs With Circular Ones," IBM Corporation Interim Report, 1978.

Segal M., "The Operator Scheduling Problem: A Network Flow Approach," Operations Research, July 1974.

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Scheduling Methds |
---|---|

Author: | Browne, Jim |

Publication: | Industrial Management |

Date: | Jan 1, 1993 |

Words: | 1853 |

Previous Article: | Greater commercial lending productivity: a strategic marketing tool for bankers. |

Next Article: | Using flextime to create a competitive workplace. |

Topics: |