Spread time considerations in operational fixed job scheduling

Date

2006-10-15

Author

Eliiyi, D. T.
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

244
views

0
downloads

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 conditions, and powerful lower and upper bounds. The computational results reveal that the branch and bound algorithm returns optimal solutions for problem instances with up to 100 jobs in reasonable solution times.

Subject Keywords

Management Science and Operations Research, Strategy and Management, Industrial and Manufacturing Engineering

URI

https://hdl.handle.net/11511/38952

Journal

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH

DOI

https://doi.org/10.1080/00207540500478645

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

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...
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 ...
Due date and cost-based FMS loading, scheduling and tool management Turkcan, Ayten; Akturk, M. Selim; Storer, Robert H. (Informa UK Limited, 2007-03-01) In this study, we consider flexible manufacturing system loading, scheduling and tool management problems simultaneously. Our aim is to determine relevant tool management decisions, which are machining conditions selection and tool allocation, and to load and schedule parts on non-identical parallel CNC machines. The dual objectives are minimization of the manufacturing cost and total weighted tardiness. The manufacturing cost is comprised of machining and tooling costs (which are affected by machining cond...
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.

Citation Formats

D. T. Eliiyi and M. Azizoğlu, “Spread time considerations in operational fixed job scheduling,” INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, pp. 4343–4365, 2006, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/38952.