Heuristics for operational fixed job scheduling problems with working and spread time constraints

Date

2011-07-01

Author

Eliiyi, Deniz Tursel
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

254
views

0
downloads

Operational fixed job scheduling problems select a set of jobs having fixed ready and processing times and schedule the selected jobs on parallel machines so as to maximize the total weight. In this study, we consider working time and spread time constrained versions of the operational fixed job scheduling problems. The working time constraints limit the total processing load on each machine. The spread time constraints limit the time between the start of the first job and the finish of the last job on each machine. For the working time constrained problem, we present a filtered beam search algorithm that evaluates the promising nodes of the branch and bound tree. For the spread time constrained problem we propose a two phase algorithm that defines the promising sets for the first jobs and finds a solution for each promising set. The results of our computational tests reveal that our heuristic algorithms perform very well in terms of both solution quality and time.

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/35079

Journal

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS

DOI

https://doi.org/10.1016/j.ijpe.2011.03.018

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

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...
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...
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...
Reassessing tradeoffs inherent to simultaneous maintenance and production planning Batun, Sakine (Wiley, 2012-03-01) Previous work has considered the simultaneous (as opposed to sequential) optimization of a maintenance policy and a production policy in a multi-product setting with random yield and product mix constraints. One of the sequential approaches to which the simultaneous approach is compared is a so-called first-come-first-served (FCFS) approach, i.e., an approach that generates randomized production policies that do not depend on the deterioration state of the machine. However, the model formulation for this ap...

Citation Formats

D. T. Eliiyi and M. Azizoğlu, “Heuristics for operational fixed job scheduling problems with working and spread time constraints,” INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, pp. 107–121, 2011, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/35079.