Formulate the following problem as a mixed integer program (do NOT solve).

A Company manufactures “n” different products having unit profits of Pi ( i = 1,2, ...., n). Each product can be manufactured on any of “m” available machines. The length of time in minutes it takes to manufacture one unit of product i on machine j is tij. If machine “j” is to be used on a particular shift, a setup time in minutes of sj is incurred. During a normal 8 hour shift, R i ( i = 1,2, ...., n), SOME units of product i must be manufactured. There are “k” operators (k<m) available to operate machines on a given shift (i.e. no more than k machines can operate on a shift). Because of a shared power source, Machine 2 can be used only if machine 1 is being used. Machines 3 and 4 share the same drive system, and therefore they cannot both operate on the same shift. To operate machines 5 or 6 will require an additional cost of ‘c’ dollars each per shift because of their unique power requirements.

The objective is to determine for a given shift, which machines to operate and how many units of each product to manufacture on each machine in order to maximize profit. Assume no machine downtime during a shift (i.e. each machine is available for 8 hours).

Let:

n = number of different products (discrete integer)

Pi = unit of profit (continuous), “i” = 1 to n (discrete integer)

tij = time to produce one unit of product “i” on machine “j” (continuous, min)

K = workers available per shift (less than # of machines available)

Ri = time available per shift (8 hr assumed) “i” = 1 to n (discrete integer)

m = number of available machines (discrete integer)

sj = set up time on machine “j” (continuous, min)

Caveats:

Machine 2 & 1 related (dependent): Machine 2 ONLY if Machine 1

Machine 3 & 4 related (dependent): Machine 3 OR Machine 4

Machine 5 & 6 penalty (cost): $c/shift

a. Define your continuous (xij ) and integer variables (yj ):

xij = # of units of product “i” (i=1..n) to manufacture on machine “j” (j=1…m)

yj = 1 if machine “j” used, else = 0 (binary flag)

**Subject Mathematics Operations Research**