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

217
views

0
downloads

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

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.