Consider a project planning example where the two criteria of interest are
F1 = Project completion time
F2 = Cost of crashing activities
We formulated this problem as a linear programming problem. To construct the efficient frontier or trade off curve between F1 and F2, we simply solve the problem:
Subject to: precedence constraints,
And F1 ≤ T
Now, we systematically vary T, the completion time, to obtain the efficient frontier. The efficient frontier is piecewise linear because F1 and F2 as well as all the constraints are linear in this problem. The key idea in this approach is that one criterion is contained in the constraint set and is parametrically varied to minimize the other criterion. The approach is also applicable when there are more than two criteria. In this more general case, all but one criterion must be brought into the constraint set and the remaining criterion is successfully optimized by varying the right hand sides of the criteria in the constraint set.
Another approach for obtaining the efficient frontier is to use a linear weighted average method. In this approach, we optimize
W1F1 + W2F2 + W3F3 + …… + WmFm
Subject to specified constraints, where
Wi ≥0, I = 1 to m
i = 1 Wi = 1
The solution of this problem, which is a simple linear program if all the F1 s and the constraints are linear, provides a point on the efficient frontier. By choosing different values of the weights, Wi, we can trace the entire efficient frontier.
This approach can be applied to product mix decisions, aggregate planning decisions, and location and distribution decisions when the appropriate criteria functions and the constraints are linear. In nonlinear cases, more complex procedures will be required to generate the efficient the efficient frontier, especially of the problem is non-convex (i.e. if the efficient contains local dips or valleys)
Many production problems, such as job shop scheduling assembly line balancing, and resources constrained project scheduling, cannot be easily solved by mathematical programming approaches. This is because even for a single criterion the size of the problem is too large to be solved in reasonable computational time. Specialized procedures that exploit problem characteristics are needed to solve such problems. Unfortunately, the transferability of these specialized procedures to other problems is negligible at this point in time. In the future, when specialized procedures are developed for a large class of important problems, some patterns of similarly may emerge.
We will demonstrate the construction of the efficient frontier for a single machine job shop scheduling problem when n jobs are available for processing at time zero. The processing time p, and the date di for each job i is known. The two criteria of interest are
F1 = Number of jobs tardy
F2 = Average flow time
The procedure for constructing the trade off curve between F1 and F2 has been developed in 1986. We will illustrate this procedure using a simple example.
In Table below the data for our example are presented. The optima solution for the number of jobs tardy criterion is given by the Moore sequence, and the optimal solution for the average flow time criterion is given by the shortest processing time (SPT) sequence. This information is as follows:
Data For single Machine Scheduling Problems
Job Processing Due date (di)
1 5 245
2 10 15
3 30 40
4 50 55
5 60 100
6 90 190
Criterion Sequence No of Jobs Tardy Average Flow time
Number of jobs tardy 2-3-5-6-1-4 1 130.00
Average flow time 1-2-3-4-5-6 4 93.30
It is clear from results that minimizing the number of jobs tardy alone ignores average flow time and thus produces a poor result on this criterion. On the other hand, minimizing flow time alone results in a poor performance on the number of jobs tardy criterion. It is likely that a manager may prefer a good solution on both criteria rather than an optimal solution on one criterion that had an associated poor solution on the second criterion.