This study considers bicriteria approaches to the minimum cost network flow problem and a rescheduling problem where those approaches find their applications.
For the bicriteria integer minimum cost network flow problem, we generate all efficient solutions in two phases. The first phase generates the extreme supported efficient points that are the extreme points of the objective space of the continuous bicriteria network flow problem. In the second phase, we generate the nonextreme supported and unsupported efficient points by Integer Programming Based approaches.
Our rescheduling problem considers parallel unrelated machine environments. The criteria are the total flow time as an efficiency measure and the total reassignment cost as a stability measure. We show that the problems that address linear functions of the two criteria can be represented by bicriteria network flow models. To generate all efficient solutions, we use a Classical Approach that is based on the optimal solutions of the singly constrained network flow problem and provide a Branch and Bound approach that starts with extreme supported efficient set and uses powerful bounds. To find an optimal solution to any nonlinear function of the two criteria, we provide a Branch and Bound approach and an Integer Programming Based approach that eliminates some portions of the efficient set that cannot provide improved solutions.
We contribute both to the network flow and scheduling literature by proposing algorithms to the bicriteria network flow models and applying them to a rescheduling problem that is bicriteria in nature.
The results of our extensive computations with up to 100 jobs and 12 machines have revealed that, the Branch and Bound algorithm finds the efficient set in less computational effort compared to the classical approach. In minimizing a nonlinear function of the two criteria both IP Based approach and Branch and Bound algorithm perform quite satisfactory.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12607822/index.pdf |
| Date | 01 November 2006 |
| Creators | Ozlen, Melih |
| Contributors | Azizoglu, Meral |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | Ph.D. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for public access |
Page generated in 0.002 seconds