METHODS/ APPROACH

This scheduling problem can be solved most expeditiously using linear programming. Let F denote the number of full-time employ- ees. Some number, F1, of them will work one hour of overtime between 5 PM and 6 PM each day and some number, F2, of the full- time employees will work overtime between 6 PM and 7 PM. There will be seven sets of part-time employees who begin their work day at hour j=j␣1,2,...,7,withP1beingthenumberofworkers beginning at 9 AM, P2 at 10 AM, . . . , P7 at 3 PM. Note that because part-time employees must work a minimum of four hours, none can start after 3 PM because the entire operation ends at 7 PM. Similarly, some number of part-time employees, Qj, leave at the end of hour j, j 4, 5, . . . , 9. The workforce requirements for the first two hours, 9 AM and 10 AM, are: F P1 14 F P1 P2 25 At 11 AM half of the full-time employees go to lunch; the remaining half go at noon. For those hours: 0.5F P1 P2 P3 26 0.5F P1 P2 P3 P4 38 Starting at 1 PM, some of the part-time employees begin to leave. For the remainder of the straight-time day: F P1 P2 P3 P4 P5 −Q4 55 F P1 P2 P3 P4 P5 P6 −Q4 −Q5 60 F P1 P2 P3 P4 P5 P6 P7 −Q4 −Q5 −Q6 51 F P1 P2 P3 P4 P5 P6 P7 −Q4 −Q5 −Q6 −Q7 29 For the two overtime hours: F P1 P2 P3 P4 P5 P6 P7 −Q4 −Q5 −Q6 −Q7 −Q8 14 F P1 P2 P3 P4 P5 P6 P7 −Q4 −Q5 −Q6 −Q7 −Q8 −Q9 9 If the left-hand sides of these 10 constraints are added, one finds that 7F hours of full-time labor are used in straight time (although 8F are paid for), F1 F2 full-time labor