(integer programming problem) In the given table, we have a list of potential em

Question

(integer programming problem) In the given table, we have a list of potential employees. For each employee, we have the time s/he wants to start and finish work and how much s/he wants to be paid for the work. The problem is to find a selection of employees so that there is at least one ( but possibly more than one) employee working at each time between 1pm and 9pm. One example of selection could be Tom, Mary, Bob. This selection has a total cost of 30+21+20=71

Formulate this problem as an Integer Programming

employee Tom Peter Marry Jerry Bob Abby Melisa hours 1-5pm 1-3pm 4-7pm 4-9pm 6-9pm 5-8pm 8-9pm amount paid 30 19 21 40 20 22 10

Explanation / Answer

Let x1 represents the time of working betweeen 1-2

Let x2 represents the time of working between 2-3

and so on Let x8 represents the time of working between 8-9

x1 + x2 + x3 + x4 = 30 (Tom Hours)

x1 + x2 = 19 (Peter Hours)

x4 + x5 + x6 = 21 (Marry Hours)

x4 + x5 + x6 + x7 + x8 = 40 (Jerry Hours)

x6 + x7 + x8 = 20(Bob Hours)

x5 + x6 + x7 = 22(Abby Hours)

x8 = 10 (melisa)

Now we want the min value of (x1+x2+...+x9) by assigning the work to employees

Only Tom works in the time frame (3-4), hence Tom needs to be selected at any cost

For reducing the cost, we should take the person working from 5 to 8 which is abby and then for last hour it will be Melissa

Least Cost = Recruit Tom + Recruit Abby + Recruit Melisa

=> 30+22+10

=> $62

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.