Flow shop-sequencing problem with synchronous transfers and makespan minimization

Date

2007-01-01

Author

Soylu, B.
Kirca, Ou
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

234
views

0
downloads

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.

Subject Keywords

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

URI

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

Journal

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH

DOI

https://doi.org/10.1080/00207540600621672

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...
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 ...
Dissimilarity maximization method for real-time routing of parts in random flexible manufacturing systems Saygin, C; Kilic, SE (Springer Science and Business Media LLC, 2004-04-01) This paper presents a dissimilarity maximization method (DMM) for real-time routing selection and compares it via simulation with typical priority rules commonly used in scheduling and control of flexible manufacturing systems (FMSs). DMM aims to reduce the congestion in the system by selecting a routing for each part among its alternative routings such that the overall dissimilarity among the selected routings is maximized. In order to evaluate the performance of DMM, a random FMS, where the product mix is...
Capacity allocation problem in flexible manufacturing systems: branch and bound based approaches ÖZPEYNİRCİ, SELİN; Azizoğlu, Meral (Informa UK Limited, 2009-01-01) This study considers an operation assignment and capacity allocation problem that arises in flexible manufacturing systems. The machines have limited time and tool magazine capacities and the available tools are limited. Our objective is to maximise total weight of assigned operations. We develop a branch and bound algorithm that finds the optimal solutions and a beam search algorithm that finds high quality solutions in polynomial time.

Citation Formats

B. Soylu, O. Kirca, and M. Azizoğlu, “Flow shop-sequencing problem with synchronous transfers and makespan minimization,” INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, pp. 3311–3331, 2007, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/34887.