Homework answers / question archive / Choose two out of these 3 questions and solve them and you can skip the ampl part it’s not needed

Choose two out of these 3 questions and solve them and you can skip the ampl part it’s not needed

Operations Management

Share With

---

Choose two out of these 3 questions and solve them and you can skip the ampl part it’s not needed.
Three different items are to be routed through three machines. Each item must be processed first on machine 1, then on machine 2, and finally on machine 3. The sequence of items may differ for each machine. Assume that the times t,;; required to perform the work on item 7 by machine ) are known and are integers. Our objective is to minimize the total time necessary to process all the items.

 

(a) Formulate the problem as an integer programming problem. (Hint. Let :r,; be the start-ing time of processing item z on machine 7 . Your model must prevent two items from occupying the same machine at the same time; also, an item may not start processing on machine (j + 1) unless it has completed processing on machine j.|

 

(b) Solve the problem in AMPL/Excel with ¢t;,; = 10,t)2 = 12,t13 = 8.tg, = 13,te2 =

10, to; = 18 and t3, = 7, t32 = 15, t33 = 12 and solve it using AMPL/Excel.

 

3. Many practical problems, such as fuel-oil delivery, newspaper delivery, or school-bus routing, are special cases of the generic vehicle-routing problem. In this problem, a fleet of vehicles must be routed to deliver (or pick up) goods from a depot, node 0, to n drop-points, 7 =

1,2,...,n. Define the following parameters:

 

l

Q,x = Loading capacity of the & th vehicle in the fleet (A = 1,2, ...,m);

d; = Number of items to be left at drop-point i (i = 1,2,...,7);

1" = Time to unload vehicle k at drop-point i (§ = 1,2,...n; kK =1,2,...,m);

ti = Time for vehicle k to travel from drop-point i to drop-point

JG =0,1,....m5 7 =O, 1,....m;k =1,2,...,m)

Gi = Cost for vehicle k to travel from node i to node j(i = 0, 1,...,a:

J =0,1,...,m;k =1,2,...,m).

If a vehicle visits drop-point 7, then it fulfills the entire demand d; at that drop-point. Only one vehicle can visit any drop-point, and no vehicle can visit the same droppoint more than once. The routing pattern must satisfy the service restriction that vehicle k’s route take longer than 7; time units to complete. Define the decision variables for this problem as: rk 1 if vehicle k& travels from drop-point 7 to drop-point 7,

‘I -) 0 otherwise

Formulate an integer program that determines the minimum-cost routing pattern to fulfill demand at the drop-points that simultaneously meets the maximum routing-time constraints and loads no vehicle beyond its capacity. Generate a problem with 20 drop-points and 5 vehicles and develop an AMPL/Excel model to solve it. Provide your own values for the

parameters Q,, d,, t®, tt. and Cy.

 

4. Suppose that a firm has N large rolls of paper, each W inches wide. It is necessary to cut

N, rolls of width W; from these rolls of paper. We can formulate this problem by defining

variables as follows:

 

x,; = Number of smaller rolls of width W, cut from large roll 7

We assume there are m different widths W;. In order to cut all the required rolls of width

W,, we need constraints of the form:

N

> i; =N,, (@=1,2,--- ,m).

j=l

Further, the number of smaller rolls cut from a large roll is limited by the width W of the

large roll. Assuming no loss due to cutting, we have constraints of the form:

S Wir; < W, (7 = 1,2, - 7° .N)

i=l

 

(a) Formulate an objective function to minimize the number of large rolls of width W used

to produce the smaller rolls.

 

(b) Reformulate the model to minimize the total trim loss resulting from cutting. Trim loss

is defined to be that part of a large roll that is unusable due to being smaller than any size needed.

 

(c) Solve the model in AMPL/Excel by generating a random instance of the problem in- volving 10 rolls of 100 inch each with 5 different sizes.