Bicriteria Rescheduling On Unrelated Parallel Machines.pdf

Melih Özlen's 2006 Ph.D. thesis in Industrial Engineering at Middle East Technical University explores a bicriteria rescheduling problem on unrelated parallel machines, focusing on network flow and enumeration-based approaches. The thesis consists of 99 pages and was supervised by Prof. Meral Azizoğlu.

Key aspects of the thesis include:

1. Bicriteria Integer Minimum Cost Network Flow Problem:
- Generates all efficient solutions in two phases: first, extreme supported efficient points (extreme points of the objective space); second, nonextreme supported and unsupported efficient points using Integer Programming Based approaches.

2. Rescheduling Problem on Parallel Unrelated Machines:
- Considers total flow time (efficiency) and total reassignment cost (stability) as criteria.
- Shows that problems addressing linear functions of the two criteria can be represented by bicriteria network flow models.
- Presents a Classical Approach and a Branch and Bound approach to generate all efficient solutions.
- Provides a Branch and Bound approach and an Integer Programming Based approach to find optimal solutions for nonlinear functions of the two criteria.

3. Contributions:
- Proposes algorithms for bicriteria network flow models and applies them to a bicriteria rescheduling problem.
- Computational results with up to 100 jobs and 12 machines show that the Branch and Bound algorithm outperforms the classical approach in finding the efficient set. Both IP Based approach and Branch and Bound algorithm perform well in minimizing a nonlinear function of the two criteria.

Keywords: Bicriteria Network Flows, Rescheduling, Parallel Unrelated Machines, Total Flowtime, Total Reassignment Cost.