Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
221
views
76
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.