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
Operational fixed job scheduling problem
Download
index.pdf
Date
2004
Author
Türsel Eliiyi, Deniz
Metadata
Show full item record
Item Usage Stats
195
views
147
downloads
Cite This
In this study, we consider the Operational Fixed Job Scheduling Problem on identical parallel machines. The problem is to select a subset of jobs for processing among a set of available jobs with fixed arrival times and deadlines, so as to maximize the total weight. We analyze the problem under three environments: Working time constraints, Spread time constraints, and Machine dependent job weights. We show that machine eligibility constraints appear as a special case of the last environment. We settle the complexity status of all problems, and show that they are NP-hard in the strong sense and have several polynomially solvable special structures. For all problems, we propose branch and bound algorithms that employ powerful reduction mechanisms and efficient lower and upper bounds. The results of our computational runs reveal that, the algorithms return optimal solutions for problem instances with up to 100 jobs in reasonable solution times.
Subject Keywords
Engineering mathematics.
URI
http://etd.lib.metu.edu.tr/upload/2/12605482/index.pdf
https://hdl.handle.net/11511/14551
Collections
Graduate School of Natural and Applied Sciences, Thesis
Suggestions
OpenMETU
Core
Spread time considerations in operational fixed job scheduling
Eliiyi, D. T.; Azizoğlu, Meral (Informa UK Limited, 2006-10-15)
In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance c...
Operational fixed interval scheduling problem on uniform parallel machines
Bekki, Oezguen Baris; Azizoğlu, Meral (Elsevier BV, 2008-04-01)
In this study, we address an operational fixed interval scheduling problem on uniform parallel machines. Our objective is to maximize the total weight of the jobs processed. We show that the problem is NP-hard in the strong sense and develop polynomial time algorithms for some special cases. We propose a branch and bound algorithm that employs dominance conditions and tight bounds. The results of our computational tests have revealed that the algorithm returns optimal solutions for problem instances with up...
Parallel-machine rescheduling with machine disruptions
Azizoğlu, Meral (Informa UK Limited, 2005-12-01)
In this study we consider a rescheduling problem on identical parallel machines. The rescheduling is undertaken because of a period of unavailability on one of the machines. We consider the total flow time as an efficiency measure and stability is gauged in terms of the number of jobs processed on different machines in the original and new schedules. We show that all efficient schedules with respect to efficiency and stability measures can be generated in polynomial time.
A fixed job scheduling problem with machine-dependent job weights
Eliiyi, D. T.; Azizoğlu, Meral (2009-01-01)
This study considers the identical parallel machines operational fixed job scheduling problem with machine-dependent job weights. A job is either processed in a fixed interval or is not processed at all. Our aim is to maximise the total weight of the processed jobs. We show that the problem with machine eligibility constraints resides as a special case of this problem. We identify some special polynomially solvable cases and propose a branch-and-bound (BB) algorithm that employs efficient bounding schemes a...
Ranking units by target-direction-set value efficiency analysis and mixed integer programming
Büyükbaşaran, Tayyar; Köksalan, Murat; Department of Industrial Engineering (2005)
In this thesis, two methods are proposed in order to rank units: Target-direction-set value efficiency analysis (TDSVEA) and mixed integer programming (MIP) technique. Besides its ranking ability based on preferences of a decision maker (DM), TDSVEA, which modifies the targeted projection approach of Value Efficiency Analysis (VEA) and Data Envelopment Analysis (DEA), provides important information to analyzer: targets and distances of units from these targets, proposed input allocations in order to project...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
D. Türsel Eliiyi, “Operational fixed job scheduling problem,” Ph.D. - Doctoral Program, Middle East Technical University, 2004.
