Need help with problem (15.7)

15.4 Project Scheduling. This problem deals with the creation of a project sched- ule; specifically, the project of building a house. The project has been divided into a set of jobs. The problem is to schedule the time at which each of these jobs should start and also to predict how long the project will take. Naturally, the objective is to complete the project as quickly as possible time is money!). Over the duration of the project, some of the jobs can be done concurrently. But, as the following table shows, certain jobs definitely can't start until others are completed. 236 15. APPLICATIONS Duration (weeks) 0 Must be preceded by 2 0 Job 0. Sign contract with buyer 1. Framing 2. Roofing 3. Siding 4. Windows 5. Plumbing 6. Electrical 7. Inside finishing 8. Outside painting 9. Complete the sale to buyer 3 3 2,4 5,6 2,4 7,8 0 One possible schedule is the following: O 10 10 0 Job Start time 0. Sign contract with buyer 0 1. Framing 1 2. Roofing 4 3. Siding 4. Windows 5. Plumbing 6. Electrical 13 7. Inside finishing 16 8. Outside painting 14 9. Complete the sale to buyer 21 With this schedule, the project duration is 21 weeks (the difference between the start times of jobs 9 and 0). To model the problem as a linear program, introduce the following decision variables: t; = the start time of job j. (a) Write an expression for the objective function, which is to minimize the project duration (b) For each job j, write a constraint for each job i that must precede j; the constraint should ensure that job j doesn't start until job i is finished. These are called precedence constraints. 15.5 Continuation. This problem generalizes the specific example of the pre- vious problem. A project consists of a set of jobs J. For each jobj E I there is a certain set P, of oth jobs that must be completed before job j can be started. (This is called the set of predecessors of job j.) One of the jobs, say s, is the starting job; it has no predecessors. Another job, sayt, is the final (or terminal) job; it is not the predecessor of any other job. The time it will take to do job j is denoted d; (the duration of the job). EXERCISES 237 The problem is to decide what time each job should begin so that no job begins before its predecessors are nished, and the duration of the entire project is minimized. Using the notations introduced above, write out a complete description of this linear programming problem. 15.6 Continuation. Let Iij denote the dual variable corresponding to the prece dence constraint that ensures job j doesn't start until job i finishes. (a) Write out the dual to the specific linear program in Problem 15.4. (b) Write out the dual to the general linear program in Problem 15.5. c) Describe how the optimal value of the dual variable rij can be inter- preted. 15.7 Continuation. The project scheduling problem can be represented on a directed graph with arc weights as follows. The nodes of the graph corre- spond to the jobs. The arcs correspond to the precedence relations. That is, if job i must be completed before job j, then there is an arc pointing from node i to node ;. The weight on this arc is d. (a) Draw the directed graph associated with the example in Problem 15.4, being sure to label the nodes and write the weights beside the arcs. (b) Return to the formulation of the dual from Problem 15.6(a). Give an interpretation of that dual problem in terms of the directed graph drawn in Part (a). (c) Explain why there is always an optimal solution to the dual problem in which each variable Iij is either 0 or 1. (d) Write out the complementary slackness condition corresponding to dual variable 226 (e) Describe the dual problem in the language of the original project scheduling model