During the next three months, Shoemaker, Inc. must meet the following demands for shoes:
month 1, 1000 pairs; month 2, 1500 pairs; month 3, 1800 pairs. It takes 1 hour of labor to produce a pair of shoes. During each of the next three months, the following number of regular-time labor hours are available: month 1, 1000 hours, month 2, 1200 hours, month 3, 1200 hours. Each month, the company can require workers to put in up to 400 hours of overtime. Workers are paid only for the hours they work, and a worker receives $4 per hour for regular-time work and $6 per hour for overtime work. At the end of each month, a holding cost of $1.5 per pair of shoes in incurred. Formulate a min-cost network ow problem (MCNFP) that can be used to minimize the total cost incurred in meeting the demand of the next three months. A formulation requires drawing the appropriate network and determining the cij 's, uij 's, bi 's. How would you modify your answer if demand could be backlogged (all demand must still be met by the end of month 3) at a cost of $20/pair/month?