Benjamin Tran, Caselyn Iglesias, Chad Creason, Kristianto Andresen, Tiran Alando

IE416

10/19/10

IE 416: Operations Research I Fall 2010

Source of the problem statement: W. L. Winston, " Operations Research, Application and Algorithms"

Solution by student groups (formulation was given)

Dr. Parisay’s comments are in red.

Post Office Problem – Example 7, Pg. 72

Problem Statement

A post office requires different numbers of full-time employees on different days of the week. The number of full-time employees required on each day is given in Table 4. Union rules state that each full-time employee must work five consecutive days and then receive two days off. For example, an employee who works Monday to Friday must be off Saturday and Sunday. The post office wants to meet its daily requirements using only full-time employees. Formulate an LP that the post office can use to minimize the number of full-time employees who must be hired.

Table 4 – Requirements for Post Office
Day / Number of Full-time Employees Required
1 = Monday / 17
2 = Tuesday / 13
3 = Wednesday / 15
4 = Thursday / 19
5 = Friday / 14
6 = Saturday / 16
7 = Sunday / 11

Summary Table

The following summary table has been derived from the information in the problem statement:

This is a good clarification.

Table 1 – Summary Table
Day Full-Time Employee Starts Shift / Minimum Number of Workers For Day / Limitations
1 = Monday / 17 / Work: Mon-Fri
Off-Work: Sat-Sun
2 = Tuesday / 13 / Work: Tue-Sat
Off-Work: Sun-Mon
3 = Wednesday / 15 / Work: Wed-Sun
Off-Work: Mon-Tue
4 = Thursday / 19 / Work: Thu-Mon
Off-Work: Tue-Wed
5 = Friday / 14 / Work: Fri-Tue
Off-Work: Wed-Thu
6 = Saturday / 16 / Work: Sat-Wed
Off-Work: Thu-Fri
7 = Sunday / 11 / Work: Sun-Thu
Off-Work: Fri-Sat

Decision Variables

These are the decision variables for this problem:

Table 2 – Decision Variables
Decision Variable / Description
X1 / Number of employees starting on Monday
X2 / Number of employees starting on Tuesday
X3 / Number of employees starting on Wednesday
X4 / Number of employees starting on Thursday
X5 / Number of employees starting on Friday
X6 / Number of employees starting on Saturday
X7 / Number of employees starting on Sunday

The results from each of these decision variables specifically show the number of workers beginning their 5-day shift on that particular day. For instance, the result for X1 represents the number of employees starting their 5-day long shift on Monday; the result for X2 represents the number of employees starting their 5-day long shift on Tuesday.

Objective Function

The goal of this problem is to minimize the number of employees to fulfill the Post Office’s daily workforce size demand. Since the decision variables quantify the number of employees starting on each day, there is no error of duplicity. Therefore, the following objective function has been made:

Eqn. 1

The result of this objective function will be the total number of employees needed in order to meet the daily labor requirements of the Post Office.

Constraints

The main constraint in this problem is the specific number of employees needed per day, as shown:

This is a good summary and clarification. This will help with formulation as indicated in the figure.

Figure 1 - General Employee Schedule

One can interpret the chart as this: “For Monday,X1, X4, X5, X6, and X7 employees will be working. And, the required number of employees working on Monday is 17 people. Therefore, the sum of X1, X4, X5, X6, and X7 must be at least 17.” It should be noted that X1 ≠ X1, because X1 means the number of employees beginning their 5-day long shift on Monday, and X1 refers to the group of employees beginning their 5-day long shift on Monday. In other words, X1 is the number of people in X1.

By using the information in Figure 1, the S.T. Equations have been created, as shown below:

Table 3 – S.T. Equations
Day / Demand of Workforce Size / S.T. Equations
Monday / 17 /
Tuesday / 13 /
Wednesday / 15 /
Thursday / 19 /
Friday / 14 /
Saturday / 16 /
Sunday / 11 /

Another constraint that should be taken into consideration is sign restriction, as shown below:

Eqn. 2

This constraint is necessary, because the essence of the problem can never allow a negative number of people. With this restriction, it prohibits the optimum solution from having any negative values for the decision variables.

WinQSB Formulation

To ease the WinQSB Formulation, the following Summary of the problem has been made:

Table 5 – Summary of Post Office Problem for WinQSB
Objective Function /
Subject-To Equations / Workforce Size / Sign Restriction

There are a total of 7 decision variables and 7 constraints rather than sign constraints. We will not need to input the sign restriction constraints. With all the information in Table 5, it is now possible to apply WinQSB. Upon loading a new problem, the following information should be entered into the Problem Specification window:

Figure 2 - WinQSB LP Problem Specification

Once the information has been entered and the “OK” button has been pressed, a new screen will load. Enter the information in Table 5 into WinQSB. It should look similar to this:

Figure 3 - WinQSB LP Problem Input

Here is an explanation of the terms found in Figure 3:

Table 6 – Notation Explanation (Refer to Table 2, 3)
St-Wrk-Mon / Number of Employees Beginning Their 5-day Shift on Monday = X1
St-Wrk-Tue / Number of Employees Beginning Their 5-day Shift on Tuesday = X2
St-Wrk-Wed / Number of Employees Beginning Their 5-day Shift on Wednesday= X3
St-Wrk-Thu / Number of Employees Beginning Their 5-day Shift on Thursday = X4
St-Wrk-Fri / Number of Employees Beginning Their 5-day Shift on Friday = X5
St-Wrk-Sat / Number of Employees Beginning Their 5-day Shift on Saturday= X6
St-Wrk-Sun / Number of Employees Beginning Their 5-day Shift on Sunday = X7
Dmd-Mon / = Demand of Employees for Monday = Monday Constraint
Dmd-Tue / Demand of Employees for Monday = Tuesday Constraint
Dmd-Wed / Demand of Employees for Monday = Wednesday Constraint
Dmd-Thu / Demand of Employees for Monday = Thursday Constraint
Dmd-Fri / Demand of Employees for Monday = Friday Constraint
Dmd-Sat / Demand of Employees for Monday = Saturday Constraint
Dmd-Sun / Demand of Employees for Monday = Sunday Constraint

After entering the information into the WinQSB, one must select “Solve the Problem,” which is under the “Solve and Analyze” tab. It should result with the following outputs:

Solution 1

Figure 4 - WinQSB LP Problem Output 1

Solution 2

Figure 5 - WinQSB LP Problem Output 2

Solution 3

Figure 6 - WinQSB LP Problem Output 3

Solution 4

Figure 7 - WinQSB LP Problem Output 4

From these outputs, it is evident that 22.33 employees is the optimal solution in order to comply with the demands of the Post Office. To apply this to the real world, it would be necessary round the optimal solution to 23 employees, because it is infeasible to hire 22.33 employees. You will learn about Integer Linear Programming that will take care of such situations later on.

The main difference between each of the solutions is the schedule of the employees, as shown below:

The following is a very good job in summarizing all alternate solutions (multi optimal solutions). This will assist in report to the manager.

Table 7 – Optimal Solution Summary
Solution 1 / Solution 2 / Solution 3 / Solution 4
# of Employees Starting Monday / 6.33 / 6 / 1.33 / 1.33
# of Employees Starting Tuesday / 5 / 5.33 / 5.33 / 3.33
# of Employees Starting Wednesday / 0.33 / 0 / 0 / 2
# of Employees Starting Thursday / 7.33 / 7.33 / 7.33 / 7.33
# of Employees Starting Friday / 0 / 0 / 0 / 0
# of Employees Starting Saturday / 3.33 / 3.33 / 3.33 / 3.33
# of Employees Starting Sunday / 0 / 0.33 / 5 / 5

Because of the difference in the scheduling, the shadow prices and the reduce costs will vary, which can be seen in Figures 4 – 7.

Sensitivity Analysis – Change Objective Function Coefficient for Monday

It is necessary to specify which solution is selected for this sensitivity analysis.

The objective function coefficient that was chosen to be analyzed is the one that affects the number of employees starting on Monday, X1. Currently, the coefficient is 1. The reason for choosing this objective function coefficient is because Monday is the start of the week, and there are many instances in which people request Monday off due to prolonging their weekends. So it would be of interest to see how the optimum value changes as the objective function coefficient changes. The motivation for this sensitivity analysis is explained very well. However, you can interpret it in another way that makes it more practical.The coefficients in objective function can be viewed as Penalty Cost that you learnt just recently. Therefore if the coefficient is more than one for Monday it means employees do not want to start on Monday. As we want to minimize objective function, then the Simplex method algorithm will try to allocate smaller value for X1 (starting on Monday), because it has higher coefficient.

The problem specifications will remain the same in WinQSB, as will the input. However, it is necessary to perform a Parametric Analysis after finding the solution to the original problem, as shown below:

Figure 8 - WinQSB LP Problem Parametric Analysis 1

The following screen will appear, after performing the Parametric Analysis:

Figure 9 - WinQSB LP Problem Parametric Analysis Output 1

In order to change the coefficients of this objective function, it would violate a constant condition. Due to the fact that each week has seven different days, we cannot physically add a multiple of any day to a given week. Therefore, every coefficient of the objective function must equal one and never deviate from that value.This explanation makes sense; however, if we look at it as penalty cost then this explanation will change.

The following is the result of selecting Graphic Parametric Analysis, as shown on the next page:

Figure 10 - WinQSB LP Problem Graphic Parametric Analysis 1

If a given week were to contain multiple days of the week we can interpret this chart to see how the optimal solution will change due an increase in the amount of a single unit day. For this example we show how an increase in the number of “Mondays” will affect the optimal solution.

Sensitivity Analysis – Change Objective Function Coefficient for Thursday

It is necessary to specify which solution is selected for this sensitivity analysis.

The objective function coefficient that I’ve chosen to analyze is the one that affects the number of employees starting on Thursday, X4. Currently, the coefficient is 1. My reason for choosing this objective function coefficient is because Thursday has the largest demand in terms of workforce size (This is a good motivation. It is better to look at coefficient as penalty cost.), so it would be of interest to see how the optimum value changes as the objective function changes.

Figure 11 - WinQSB LP Problem Parametric Analysis 2

The following screen will appear, after performing the Parametric Analysis, as shown on the next page:

Figure 12 - WinQSB LP Problem Parametric Analysis Output 1

The information from this table states that the optimum value of the problem changes as the objective function coefficient changes. This is illustrated in the “To OBJ Value” when it is less than 23, which is the optimum value from the original problem. The optimum value reduces to less than 23 only when the coefficient changes from 1 to 0. When the coefficient is greater than 1, then the objective function increases.

In a situation like this, the objective function value would change only if there were multiple of the same day in one week or there was an elimination of one day from a week. For example, changing the objective function coefficient for Thursday from 1 to 2 would mean that there are 2 Thursdays in one week (This will change if looking at coefficient as penalty cost.). Furthermore, changing the objective coefficient for Thursday from 1 to 0 would mean that there are 0 Thursdays in one week. The latter would be useful if there were specific parameters that stated a particular day of the week needed to be eliminated from the objective function. (This is a very good discussion. It demonstrates Critical Thinking .) However, increasing the coefficient to greater than 1 would mean there were multiplies of the same day per week, which would not make sense in a real world application.

The following is the result of selecting Graphic Parametric Analysis, as shown on the next page:

Figure 13 - WinQSB LP Problem Graphic Parametric Analysis 1

This graph demonstrates that the optimal solution (z) increases as the objective function coefficient increases. The maximum the optimal solution will be 26, which is achieved when the objective function coefficient is increased to 1.5. At this point, the optimal solution will remain at 26, even if the objective function coefficient increases.

Sensitivity Analysis – Change Right Hand Side for Monday

It is necessary to specify which solution is selected for this sensitivity analysis.

The right hand side, also known as R.H.S., that was chosen to be analyzed is the one that affects the number of employees needed for Monday, the Monday Constraint. Currently, the R.H.S. value is 17 people. The reason for choosing this objective function coefficient is because Monday is the start of the week, and there are many instances in which people request Monday off due to prolonging their weekends. (This is not a good motivation. The total number required on any day should not depend on how employees want to work, but on the workload and job requirements for that day.) Therefore, the demand for Monday may change. So it would be of interest to see how the optimum value changes as the objective function coefficient changes.

The problem specifications will remain the same in WinQSB, as will the input. However, it is necessary to perform a Parametric Analysis, as shown below:

Figure 14 - WinQSB LP Problem Parametric Analysis 3

The following screen will appear, after performing the Parametric Analysis, as shown below:

Figure 15 - WinQSB LP Problem Parametric Analysis Output 3

In this sensitivity analysis, we look at changing the right hand side value of minimum number of employees to begin their shift on Mondays.

The following is the result of selecting Graphic Parametric Analysis, as shown below:

Figure 16 - WinQSB LP Problem Parametric Analysis Output 3

This graph represents how the optimal solution will deviate due to the change in the number of minimum employees required to begin their shift on Mondays. Due to the fact that the motivation would be to increase this right hand side number, we learn that the blue dot on the graph would move to the right on the red line. We can easily interpret to what value the optimal solution would be at.

This graph only represents a bug in the WinQSB software! You needed to repeat the steps and get the correct graph. I mentioned it in one of my handouts!

Sensitivity Analysis – Change Right Hand Side on Thursday

It is necessary to specify which solution is selected for this sensitivity analysis.

(Please refer to my comments for previous SA. This is not right.)

The right hand side, also known as R.H.S., that was chosen to be analyzed is the one that affects the number of employees needed for Thursday, the Thursday Constraint. Currently, the R.H.S. value is 19 people. The reason for choosing this objective function coefficient is because Thursday has the largest demand in terms of workforce size, and it would be interesting to see how the optimum solution changes as the R.H.S. changes.

The problem specifications will remain the same in WinQSB, as will the input. However, it is necessary to perform a Parametric Analysis, as shown on the next page:

Figure 17 - WinQSB Parametric Analysis Input 4

The following screen will appear, after performing the Parametric Analysis, as shown on the next page:

Figure 18 - WinQSB LP Problem Parametric Analysis Output 4

The following is the result of selecting Graphic Parametric Analysis, as shown on the next page:

Figure 19 - WinQSB LP Problem Parametric Analysis Output 4

This graph is most probably wrong and due to a bug in the WinQSB software! You needed to repeat the steps and get the correct graph. I mentioned it in one of my handouts!

The sensitivity analysis shows that the optimum value for this problem changes as the R.H.S changes. For instance, if the number of required labor workforce for Thursday changes to less than 19 people, then the optimum value will decrease from 23 people to 16 - 17 people. Furthermore, if the requirement increases above 19 people, then the optimum value will increase as well. In fact, there is a direct relationship between the demand for Thursday and the optimal solution; when the demand for Thursday increases, then the optimal solution increase as well.

In this situation, it makes sense to perform a sensitivity analysis with the R.H.S. This is because the requirement in terms of labor hours can change. As a result, it is good to understand the changes that may occur.

Report to Manager

You should specify which one of optimal solutions have been used for the following.

In this problem; the minimum amount of worker needed in each week is actually 22.333 workers with the schedule as follow:

Table - Optimum Schedule
Shift-Start Day / Number of Employees
Monday / 6.333
Tuesday / 5
Wednesday / .3333
Thursday / 7.333
Friday / 0
Saturday / 3.333
Sunday / 0

The problem with the data above is that there is no way this company says “we need six and a third of a person to work on Monday.” In order to find the best solution that makes sense: we have to eliminate fraction in our calculation. When we use integer value;the minimum number of workers required for each week is 23 workers with their schedule as follow:

Table - Optimum Schedule
Shift-Start Day / Number of Employees
Monday / 7
Tuesday / 5
Wednesday / 1
Thursday / 8
Friday / 0
Saturday / 2is modified later on
Sunday / 0

Since we haven’t discuss about integer; if we don’t use integer values and round all decimal number up; the minimum worker required will be 25 with the format as follow. This is a good discussion for now, though we will learn about ILP later on. You need to talk about alternate solutions and how it provides flexibility in decision making.