A hospital with ten operating rooms (OR) must schedule surgeries every day. Each operating room, when it is used, is budgeted for eight hours. There is a fixed cost of $4,800 to staff an open room, and once the OR is opened, this cost is incurred whether or not it is used. Assume that the duration of the procedures is known with certainty as given in the table below. The first column of the table below represents the surgeon identifier and the second column is the duration of the procedure in hours. A surgeon may have multiple procedures.

Procedures Duration

s0390 2.17

s1532 2.58

s1802 2.75

s2734 6

s2734 5.5

s2770 1.83

s5173 3.33

s6820 1

s6930 4.67

s7099 3.25

s7270 2.75

s8487 4.67

s8512 4.25

s8526 2.5

s8534 0.58

s8534 0.42

s9564 1.67

s9564 1.17

Develop a Linear Integer Programming model to help the hospital efficiently (minimum cost) schedule the procedures. Assume that a surgeon can operate in two rooms at the same time.

Assume that all the surgeons with multiple procedures cannot be in two rooms at the same time, i.e., the procedures must be performed consecutively, even if the operating room is used more than the budgeted eight hours. Find the schedule that minimizes costs and satisfies the surgeons’ needs.

Assume that you can extend the use of operating rooms more than the 8 regular budgeted hours at a cost of $1600 per hour per OR. Find an optimal schedule that minimizes costs. (Hint: You do not need to consider the use of a linear model here. i.e., you can develop a nonlinear integer programming model).