Problems

1. A construction company has a contract to construct an access ramp from a street to an expressway. The principal activities in the project are shown below, along with the scheduled starting date and the estimated number of working days which each step will require.

The company works the customary five-day week and observes holidays on Memorial Day

(May 27) and on the 4th and 5th of July. Here is a calendar for May, June, and July:

1. Construct a Gantt Progress Chart as of May 6, showing the schedule of the activities List the activities on the vertical axis and count only working days on the horizontal axis (May 6 = 1).
2. Assume it is June 10. Here Is the history of the project to-date:
   Drawing the blueprints started on May 6 and took nine working days.
   Constructing the temporary bypass road took six working days, because of heavy rains.
   The rains caused a two-day delay in commencing to build the grade, which actually started on May 22, and is incomplete as of June 10.
   Laying the foundation for the pavement commenced on June 3. and is incomplete as of June 10.
   Prepare the updated Gantt Progress Chart which shows the status of the access ramp on June 10.

2. The Interstate Biology Machines Company leases equipment to hospitals and laboratory for use in medical tests and research on humans and animals. The company has several bureaus in Cities A, B, C and D, which are staffed by technicians who may be sent to customers’ establishments in the event of difficulty with the equipment. One day, requests for service have been received from customers in Cities, 1, 2, 3, 4 and 5. The distance each service bureau to each customer, one way, is given in the table below in kilometers.

It is necessary to assign the technicians to the customers so as to minimize the amount of

technicians' travel.

1. What is the initial table for solving this problem with the assignment method?
2. What is the final table?
3. Which technician should be assigned to which customers?
4. What is the total round-trip distance which the technicians must travel?
5. Who does without in this schedule?

3. (One step beyond.) Refer to Problem #2.

1. The Service Bureau in City C is not equipped to handle the problem of Customer #1 Incorporate this constraint into the problem.
2. Customer #3 has an emergency; if the equipment is not serviced immediately, the patient may die. Incorporate this constraint into the problem.
3. What is the initial tableau?
4. What is the final tableau?
5. Which technician should be assigned to which customer?
6. What is the total round trip distance which the technicians must travel?
7. Who does without in this schedule?

4. A number of jobs are waiting to be processed at a work center. The jobs are listed below in the order in which they arrived. For each job, the due date is showing and an estimate of the processing time in workdays. Only one job can be processed at a time, and it is necessary to determine the sequence. It is now October 1.

1. What is the sequence using the first come first served (FCFS) priority rule?
2. What is the average flow time?
3. What is the average tardiness?
4. What is the makespan?
5. What is the average number of jobs at the work center?

5. Refer to Problem #4.

1. What is the sequence using the shortest processing time (SPT) rule?
2. What is the average flow time?
3. What is the average tardiness?
4. What is the makespan?
5. What is the average number of jobs at the work center?

6. Refer to Problem #4.

1. What is the sequence using the earliest due date (EDD) rule?
2. What is the average flow time?
3. What is the average tardiness?
4. What is the makespan?
5. What is the average number of jobs at the work center?

7. Refer to Problem #4.

1. What is the sequence using the critical ratio?
2. What is the average flow time?
3. What is the average tardiness?
4. What is the makespan?
5. What is the average number of jobs at the work center?

8. Which sequencing rule in #4, 5, 6, 7 produces the best production schedule?

9. A number of jobs are waiting to be processed through two work centers. Each job must be processed through Center A and Center B, in that order. For each job, the processing time in each work center is given below, in minutes.

1. Use Johnson’s rule to determine the sequence in which the jobs should be processed.
2. Construct a chart showing the sequence of the jobs in each work center, the times the jobs spend waiting, and the times that the work centers are idle.
3. What is the throughput (makespan) time?
4. How much time do the jobs spend waiting to be processed?
5. How much idle time do the work centers have?

Solutions

1. List the calendar working days, and count them off, starting with May 6. The count numbers will lie on the x-axis: May 6 = 1; July 12 = 47.

2. a. Since the table is not square, a dummy Bureau will be required.

b. Subtract the minimum number in each row, marked with brackets above, from every entry in the row. Subtract the minimum number in each column (0) from every entry in the column. The result is:

The zeroes in this tableau may be covered with four lines in at least two ways, one of which is show above. The algorithm is not finished. Subtract the minimum unlined number, marked with brackets, from all of the unlined numbers and add it to values at the intersections of the lines. The result is:

In the above tableau, a minimum of five lines is required to cover all of the zeroes, and the algorithm is finished.

c,d. One assignment of a technician to a customer must be made in each row of the final tableau. Start with rows with only one zero, and check off a row and a column for each assignment.

e. Because the dummy is assigned to Customer #3, Customer #3 will not receive a service call.

3. a. Replace the 90 in cell #C-1 with 1,000.
b. Replace the 80 in cell #B-3 with 0.
c.

d. Perform the algorithm explained in #2-b. The final tableau is:

e,f.

g. Customer #1 does not receive a service call.

4. a. The FCFS sequence is the order of arrival: 1, 2, 3, 4, 5, 6.

*Just count the calendar days. Oct. 2 =1, Oct. 3 = 2, etc.

**Flow Time – Days Available <a onClick="window.open('/olcweb/cgi/pluginpop.cgi?it=gif::Image122::/sites/dl/free/0072443901/24520/Image122.gif','popWin', 'width=NaN,height=NaN,resizable,scrollbars');" href="#"><img valign="absmiddle" height="16" width="16" border="0" src="/olcweb/styles/shared/linkicons/image.gif">Image122 (0.0K)</a>Image122 0.

Average flow time = 179/6 = 29.83 days.

1. Average tardiness = 33/6 = 5.50 days.
2. Makespan = 52 days.
3. Average number of jobs = total flow time/makespan = 179/52 = 3.44 jobs.

5. a. The SPT rule is from shortest to longest processing time.

1. Average flow time = 162/6 = 27 days.
2. Average tardiness = 7/6 = 1.17 days.
3. Makespan = 52 days.
4. Average number of jobs = total flow time/makespan = 162/52 = 3.12 jobs.

5. a. The EDD rule is from earliest to latest due date.

1. Average flow time = 183/6 = 30.5 days.
2. Average tardiness = 0.
3. Makespan = 52 days.
4. Average number of jobs = 183/52 = 3.52 jobs.

7. a. The critical ratio is the ratio of processing time to remaining time available. The job with the smallest ratio is processed.

*6/71 = 0.08

*10/37 = 0.27

*10/28 = .36

*10/20 = .50

*10/8 = 1.25

The sequence of jobs is 1, 5, 3, 4, 6, 2.

Average flow time = 173/6 = 28.83 Days.

1. Average tardiness = 22/6 = 3.67 days.
2. Makespan = 52 days.
3. Average number of jobs = 173/52 = 3.33 jobs.

8. To some extent it depends on management's priorities. If the objective is to process every order on time, then the EDD rule would be chosen. If the objective is to have as few jobs as possible cluttering up the plant, then the SPT rule would be chosen. The FCFS rule is highly unsatisfactory because it has the greatest average tardiness. Personally, I think I would pick the SPT rule, but you may have a different preference.

9. a. The first few steps in the algorithm are:

1) The shortest processing time is 8 minutes for job B in work center A. Schedule B first.
2) The next shortest time is 9 minutes for job C in work center B. Schedule C last.
3) The next shortest time is 10 minutes for job A in work center A. Schedule A second.

Proceeding in this manner produces this sequence: B, A, D, F, G, E, C.

b.

c. The throughput time is the length of time from beginning the first job to finishing the last job. It is 108 minutes on the diagram for 6b.
d. Jobs A and G have waiting time. The total waiting time is: (23 - 18) + (68 - 66) = 7 minutes.
e. Work center B has 5 idle periods. The total idle time is: 8 + (38 - 35) + (55 - 49) + (84 - 82)
+ (99 - 94) = 24 minutes. It is customary to ignore the idle time of work center A while work center B is finishing up.