Another Integer Programming Example

The campus computer store has decided to hire some students to work part time helping customers and performing various functions that used to be contracted out to outside vendors.

There are two work shifts per day (AM and PM), five days per week. Exactly one student must be assigned to work each shift. To become sufficiently familiar with the store's operation, each student hired must work at least two shifts per week. The store has identified a pool of eight qualified students from which to hire.

For each student, the store has estimated how much he or she would add to the store's profit, per shift worked. This information is shown in the table below. The table also marks each shift for which a particular student is available with a "1". Finally, it also give the maximum number of shifts per week that each student can work.

Availability |
||||||||||||

Mon |
Tue |
Wed |
Thu |
Fri |
||||||||

Initials |
Profit/Shift |
AM |
PM |
AM |
PM |
AM |
PM |
AM |
PM |
AM |
PM |
Max shifts |

CM | $ 100 | 1 | - | - | - | 1 | 1 | 1 | - | - | - | 3 |

FI | $ 50 | - | 1 | - | 1 | - | 1 | - | 1 | - | 1 | 4 |

GR | $ 95 | - | 1 | - | - | - | 1 | - | 1 | 1 | - | 2 |

HS | $ 75 | - | - | 1 | - | - | - | - | - | 1 | 1 | 2 |

JD | $ 70 | - | - | - | - | 1 | - | - | - | 1 | - | 2 |

JE | $ 90 | - | - | - | - | - | - | 1 | 1 | 1 | - | 2 |

SR | $ 80 | 1 | - | - | 1 | 1 | - | - | 1 | 1 | 1 | 3 |

TR | $ 85 | - | 1 | - | - | - | 1 | - | - | - | 1 | 2 |

To maximize its profit, which students should the store hire, and which shifts should each student work?