IE 3082Exam #1Spring 1996

1.For the n / 1 / ri 0 / Cmax problem show that scheduling the jobs based on earliest release time, i.e. the job with the smallest release time goes first, the job with the second smallest release time goes second, etc., is optimal.

2.A computer systems consultant is under contract to carry out seven projects, all with deadlines, measured in days from now. The consultant must start and complete each project sequentially. Under the terms of the contract, the consultant will receive $800 for each project completed on time, but will incur $500 in penalties for each project completed late. Each project has an associated duration which is given below. How should the projects be sequenced in order to maximize the net revenues?

Project ID1234567

Duration2468101214

Deadline6123019121824

3.You are the scheduling manager for Bryan’s Production Company. Bryan believes that plant costs are directly proportional to the amount of time that jobs are in the plant and therefore he wants to minimize the flowtime of jobs in his plant. Bryan wonders if reducing the batch sizes in the plant would reduce the total flowtime and has come to you for an answer. Reducing the batch sizes would incur some additional costs in terms of material handling but he feels that those costs would be offset by gains resulting from reduced flowtime for the jobs if in fact total flowtime could be reduced. Thus, he only wants to reduce the batch size if it would be beneficial in reducing total flowtime. Note by reducing the batch sizes I mean that instead of having n jobs with processing times pi for i=1,2,...,n we would now have 2n jobs with processing times pi and pi for i=1,2,...,n where p1 = p1 = 0.5 * p1, p2 = p2 = 0.5 * p2, and pn = pn = 0.5 * pn. For the two settings described below justify whether or not the batch sizes should be reduced.

a. n / 1 / ri 0 / F

Assume in the case of the two batches for each job that

1. r1 = r1 = r 1 , ..., rn = rn = rn and

2. The flowtime for a job is equal to the completion time of the batch that finishes last. For example, F1 = max ( F1 ,F1 ), ... ,Fn = max ( Fn ,Fn ).

b. n / 1 / precedence / F

Assume in the case of the two batches for each job that

1. If i < j then both job j and job j must not begin until both i and i are finished.

2. The flowtime for a job is equal to the completion time of the batch that finishes last. For example, F1 = max ( F1 ,F1 ), ... ,Fn = max ( Fn ,Fn ).

4.Devise a branch-and-bound algorithm to solve the total earliness problem n / 1 / / E. State it in sufficient detail to program on a computer. Assume that the jobs must finish on time and that there is a feasible schedule where this is possible.