We have a group of seven jobs j1, . . . , j7 to be executed in one machine. Each

Question

We have a group of seven jobs j1, . . . , j7 to be executed in one machine. Each job ji takes time pi and has an associated profit vi when executed. The processing times and profits are given as follows:

j1 j2 j3 j4 j5 j6 j7

processing time (in hours) 5 4 2 6 8 3 5

profit (in pounds) 9 12 5 10 14 6 12

We would like to schedule a subset of the jobs in order to maximize the profit, subject to constraints: • The total processing time of all jobs scheduled on the machine should not exceed 15 hours; • The total processing time of the scheduled jobs from j1, j2, j3, j4 should not exceed 5 hours; • The total processing time of the scheduled jobs from j5, j6, j7 should not exceed 9 hours; • Jobs j6 and j7 cannot be scheduled together. Formulate the problem as an Integer linear programming.

Explanation / Answer

Maximize: 5J1+4J2+2J3+6J4+8J5+3J6+5J7+9J1+12J2+5J3+10J4+14J5+6J6+12J7

Subject to

5J1+4J2+2J6+6J4<=5

8J5+3J6+5J7<=9

J6-J7>=0

J1,J2,J3,J4,J5,J6,J7>=0

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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