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 interval scheduling problem on uniform parallel machines
Date
2008-04-01
Author
Bekki, Oezguen Baris
Azizoğlu, Meral
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
213
views
0
downloads
Cite This
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 to 70 jobs very quickly.
Subject Keywords
Management Science and Operations Research
,
Economics and Econometrics
,
Industrial and Manufacturing Engineering
,
General Business, Management and Accounting
URI
https://hdl.handle.net/11511/35760
Journal
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
DOI
https://doi.org/10.1016/j.ijpe.2007.06.004
Collections
Department of Industrial Engineering, Article
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...
A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems
Chung, CS; Flynn, J; Kirca, O (Elsevier BV, 2002-10-11)
The m-machine permutation flowshop problem with the total flow-time objective is a common scheduling problem, which is known to be NP-hard for m greater than or equal to 2. In this article, we develop a branch and bound algorithm to solve both the weighted and unweighted version of this problem. Our algorithm incorporates a new machine-based lower bound and a dominance test for pruning nodes. Computational experiments suggest that the algorithm can handle test problems with n less than or equal to 15. It al...
Operational fixed job scheduling problem under spread time constraints: a branch-and-price algorithm
Solyali, O.; Ozpeynirci, O. (Informa UK Limited, 2009-01-01)
This study addresses the operational fixed job scheduling problem under spread time constraints. The problem is to select a subset of jobs having fixed ready times and deadlines for processing on identical parallel machines such that total weight of the selected jobs is maximised. We first give a mathematical formulation of the problem and then reformulate it using Dantzig-Wolfe decomposition. We propose a branch-and-price algorithm that works on the reformulation of the problem. Computational results show ...
Working time constraints in operational fixed job scheduling
Eliiyi, Deniz Tuersel; Azizoğlu, Meral (Informa UK Limited, 2010-01-01)
In this study we consider the operational fixed job scheduling problem under working time limitations. The problem has several practical implications in both production and service operations; however the relevant research is scarce. We analyse pre-emptive and non pre-emptive versions of the problem and its special cases. We provide polynomial-time algorithms for some special cases. We show that the non pre-emptive jobs problem is strongly NP-hard, and propose a branch-and-bound algorithm that employs effic...
Flow shop-sequencing problem with synchronous transfers and makespan minimization
Soylu, B.; Kirca, Ou; Azizoğlu, Meral (Informa UK Limited, 2007-01-01)
This study considers a permutation flow shop-sequencing problem with synchronous transfers between stations. The objective is to minimize the makespan. It is shown that the problem is strongly NP-hard. A branch-and-bound algorithm together with several lower and upper bounding procedures are developed. The algorithm returns optimal solutions to moderate-sized problem instances in reasonable solution times.
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
O. B. Bekki and M. Azizoğlu, “Operational fixed interval scheduling problem on uniform parallel machines,”
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
, pp. 756–768, 2008, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/35760.