A bicriteria rescheduling problem on unrelated parallel machines : network flow and enumeration based approaches

Download

index.pdf

Date

2006

Author

Özlen, Melih

Metadata

Show full item record

Item Usage Stats

240
views

83
downloads

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.

Subject Keywords

Bicriteria scheduling

URI

http://etd.lib.metu.edu.tr/upload/12607822/index.pdf
https://hdl.handle.net/11511/16527

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

A simulated annealing approach to bicriteria scheduling problems on a single machine Karasakal, Esra (2000-08-01) In this paper, we apply a simulated annealing approach to two bicriteria scheduling problems on a single machine. The first problem is the strongly NP-hard problem of minimizing total flowtime and maximum earliness. The second one is the NP-hard problem of minimizing total flowtime and number of tardy jobs. We experiment on different neighbourhood structures as well as other parameters of the simulated annealing approach to improve its performance. Our computational experiments show that the developed appro...
Using genetic algorithms for single-machine bicriteria scheduling problems Köksalan, Mustafa Murat; Keha, AB (2003-03-16) We consider two bicriteria scheduling problems on a single machine: minimizing flowtime and number of tardy jobs, and minimizing flowtime and maximum earliness. Both problems are known to be NP-hard. For the first problem, we developed a heuristic that produces an approximately efficient solution (AES) for each possible value the number of tardy jobs can take over the set of efficient solutions. We developed a genetic algorithm (GA) that further improves the AESs. We then adapted the GA for the second probl...
A Resource Constrained Project Scheduling Problem With Multi-Modes Altintas, Cansu; Azizoğlu, Meral (2020-01-01) In this study, the authors consider a project scheduling problem with a single non-renewable resource. The authors assume that the resource is released at scheduled times and specified quantities and the resource is consumed at activity completion. The activities can be processed at different modes where a mode is defined by a processing time and a resource requirement amount. The problem is to select the modes and timings of the activities so as to minimize the project completion time. The authors give a m...
An optimal procedure for the coordinated replenishment dynamic lot-sizing problem with quantity discounts Chung, CS; Hum, SH; Kirca, O (2000-12-01) We consider in this paper the coordinated replenishment dynamic lot-sizing problem when quantity discounts are offered. In addition to the coordination required due to the presence of major and minor setup costs, a separate element of coordination made possible by the offer of quantity discounts needs to be considered as well. The mathematical programming formulation for the incremental discount version of the extended problem and a tighter reformulation of the problem based on variable redefinition are pro...
A fast and optimal static segment scheduling method for FlexRay v3.0 ÇAKMAK, CUMHUR; Schmidt, Şenan Ece; Schmidt, Klaus Verner (2017-06-29) We propose a novel and fast frame scheduling method for the Static Segment (SS) of the new in-vehicle network standard FlexRay v3.0 in this paper. The proposed methods assigns frames to the SS using the minimum number of time slots based on an Integer Linear Programming formulation. Different. from the existing method in the literature, the proposed method computes optimal frame schedules within miliseconds.

Citation Formats

M. Özlen, “A bicriteria rescheduling problem on unrelated parallel machines : network flow and enumeration based approaches,” Ph.D. - Doctoral Program, Middle East Technical University, 2006.