1
Moehl
Martin Moehl
Dr. Parisay
IE 416 – Hw#6
9 November, 2010
HW#6
Page 75, problem 1: branch on “full-Thurs” and then “full-Sat”
a) Using LP option of WinQSB and creating the branch-and-bound tree up to two levels as assigned. Document input and output for each subproblem.
b) Using ILP option of WinQSB solve the problem.
Dr. Parisay’s comments are in red.
Problem Statement
In the post office example, suppose that each full-time employee works 8 hours per day. Thus, Monday’s requirement of 17 workers may be viewed as a requirement of 8(17) = 136 hours. The post office may meet its daily labor requirements by using both full-time and part-time employees. During each week, a full-time employee works 8 hours a day for five consecutive days, and part-time employee works 4 hours a day for five consecutive days. A full-time employee costs the post office $15 per hour, whereas a part-time employee (with reduced fringe benefits) costs the post office only $10 per hour. Union requirements limit part-time labor to 25% of weekly labor requirements. Formulate an LP to minimize the post office’s weekly labor costs.
Tables
Here is the table from the original Post Office Problem:
Employee Requirements for the Post OfficeDay / 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
Given that each full time shift is 8 hours, we can calculate the required hours needed for each day. This is done by multiplying the number of employees needed each day by eight. Doing this produces the following table:
Hour Requirements for the Post OfficeWork Day / Number of Labor Hours Required
1 = Monday / 136
2 = Tuesday / 104
3 = Wednesday / 120
4 = Thursday / 152
5 = Friday / 112
6 = Saturday / 128
7 = Sunday / 88
It is also beneficial to have a table comparing Full-time workers to Part-Time workers. This table is as follows:
Full-Time and Part-Time ComparisonCategory / Hours/Day / Rate/Hour / Constraint
Full-Time / 8 / $15 / Work 5 consecutive days
With 2 consecutive days off
Part-Time / 4 / $10 / Work 5 consecutive days
With 2 consecutive days off
Can only be 25% of total labor hours
Decision Variables
At this point it is necessary to define the decision variables. There should be a decision variable for both Full-Time and Part-Time workers for each day of the week employees start work, since the number of each is flexible within the constraints of the problem statement. The decision variables are as follows:
Decision VariablesDecision Variable / Description
FT1 / Number of Full-Time employees starting on Monday
FT2 / Number of Full-Time employees starting on Tuesday
FT3 / Number of Full-Time employees starting on Wednesday
FT4 / Number of Full-Time employees starting on Thursday
FT5 / Number of Full-Time employees starting on Friday
FT6 / Number of Full-Time employees starting on Saturday
FT7 / Number of Full-Time employees starting on Sunday
PT1 / Number of Part-Time employees starting on Monday
PT2 / Number of Part-Time employees starting on Tuesday
PT3 / Number of Part-Time employees starting on Wednesday
PT4 / Number of Part-Time employees starting on Thursday
PT5 / Number of Part-Time employees starting on Friday
PT6 / Number of Part-Time employees starting on Saturday
PT7 / Number of Part-Time employees starting on Sunday
Objective Function
At this point it is easy to produce an objective function. The goal of the objective function is to minimize cost based one how many Full-Time and Part-Time hours are worked each day. Based on this concept the basic formula becomes:
By plugging in the actual Decision Variables, the following objective function is created:
Constraints
By thinking about the problem by which day employees would work depending on which days they start, the following summary table can be produced:
*this table was copied from the group that previously solved this problem for homework.
This table shows how the total hours per day is the summation of all people working that day as defined by the day they work. Since workers can only work five consecutive days, they will have the sixth and seventh day of the week from they day they started off. Note that when summing hours, the constraints for Full-time workers is multiplied by 8 since such workers work 8 hours per shift. Similarly constraints for Part-Time employees are multiplied by 4 since they only work for hours per shift.
Based on this table, the following constraints are derived:
Constraint EquationsDay / Demand of Labor Hours / S.T. Equations
Monday / 136 /
Tuesday / 104 /
Wednesday / 120 /
Thursday / 152 /
Friday / 112 /
Saturday / 128 /
Sunday / 88 /
Note that the problem specifies that the total amount of Part-Time Labor can only be 25% of the total labor. This means that part time labor hours divided by total labor hours cannot be more than 0.25. We can write this as a general equation:
By plugging in the corresponding decision variables we get:
This can be re-written as:
This Constraint will satisfy the rule that Part-Time workers can only work 25% of the total required hours.
The only last constraint that must be specified is the sign constraint for all decision variables. It can be formulated as:
Initial WinQSB Input
At this point the problem can be inputted into WinQSB, as the objective function and all constraints are defined. First the problem will be solved using the regular linear program solving method. After WinQSB finds a solution we will try to produce an integer solution using a branch-and-bound tree. We will first branch off of an integer value for Full Time Thursday Employment. After that we will branch off of Full-Time employment for Saturday Employment. The initial input into WinQSB is as follows:
Initial WinQSB Output
Note: This solution is different from the one posted on web site before. In that solution Z=12350!!!
Assuming this solution is correct, the rest is correct.
The next step was to bound Thursday’s value to 4 employees or less. The WinQSB Input was as follows: Notice that theadded constraint is: FT4=<4
And the output was:
At this point Saturday was inspected. First the value was set low and bound to 3 employees or less. The input was as follows: Notice that theadded constraints are: FT4=<4, FT6=<3
And the output was:
After this the output for Saturday was set to 4 employees or more. The input was this: Notice that theadded constraints are: FT4=<4, FT6=>4
And the output was this:
Note that this made the value for Saturday become much less than 4. This shows that at each branch the output can change drastically.
At this point we need to go back to the first branch at Thursday, and set it to the higher integer. To do this we create a constraint that states it must be greater than or equal to 5. The input was as follows:Notice that theadded constraint is: FT4=>5
And the output was:
At this point Saturday was once again selected. It was first set to 3 employees or less. The input was as follows:Notice that theadded constraints are: FT4=>5, FT6=<3
And the output was:
Next the value for Saturday was set to the higher integer. It was set to 4 employees or more. The input was as follows:Notice that theadded constraints are: FT4=>5, FT6=>4
And the output was:
Note that on every one of the previously explored outputs there are alternative solutions. This means that this problem is a very open ended one. For the sake of demonstrating the branch-and-bound concept, one iteration of each solution is enough.
All of this input and output from WinQSB can be confusing. For that reason, the following visual branch and bound breakdown was arranged.
Notice that:
- In general Z value increases as we go down the tree. However, Z can stay the same as in Node 1, 5, and 6.
- When we branch on a variable, it will have integer value in the next immediate node. However, it can become non-integer later on. An example is the value of FT4=4 in Node 2 that is changed to FT4=2.7 in Node 4.
ILP solution
Lastly the Integer WinQSB output was found using the initial conditions, and the Nonnegative Integer function within WinQSB. The input was as follows:
And the out put was:
Note that this time no alternative solutions exist.
1