A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems

Date

2002-10-11

Author

Chung, CS
Flynn, J
Kirca, O

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

194
views

0
downloads

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 also seems capable of dealing with larger problems for the unweighted objective, especially when the processing times are correlated.

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

Journal

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS

DOI

https://doi.org/10.1016/s0925-5273(02)00234-7

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems Chung, Chia-Shin; Flynn, James; Kırca, Ömer (Elsevier BV, 2006-10-01) The m-machine permutation flowshop problem with the total tardiness objective is a common scheduling problem, which is known to be NP-hard. Here, we develop a branch and bound algorithm to solve this problem. Our algorithm incorporates a machine-based lower bound and a dominance test for pruning nodes. We undertake a numerical study that evaluates our algorithm and compares it with the best alternative existing algorithm. Extensive computational experiments indicate that our algorithm performs better and ca...
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...
An interactive algorithm for multiobjective ranking for underlying linear and quasiconcave value functions TEZCANER ÖZTÜRK, DİCLEHAN; Köksalan, Mustafa Murat (Wiley, 2019-07-29) We develop interactive algorithms to find a strict total order for a set of discrete alternatives for two different value functions: linear and quasiconcave. The algorithms first construct a preference matrix and then find a strict total order. Based on the ordering, they select a meaningful pair of alternatives to present the decision maker (DM) for comparison. We employ methods to find all implied preferences of the DM, after he or she makes a preference. Considering all the preferences of the DM, the pre...
Heuristics for operational fixed job scheduling problems with working and spread time constraints Eliiyi, Deniz Tursel; Azizoğlu, Meral (Elsevier BV, 2011-07-01) 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...
An exact algorithm for the minimum squared load assignment problem Karsu, Özlem; Azizoğlu, Meral (Elsevier BV, 2019-06) In this study, we consider an assignment problem with the objective to minimize the sum of squared loads over all agents. We provide mixed integer nonlinear and linear programming formulations of the problem and present a branch and bound algorithm for their solution. The results of our computational experiment have shown the satisfactory behavior of our branch and bound algorithm.

Citation Formats

C. Chung, J. Flynn, and O. Kirca, “A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems,” INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, pp. 185–196, 2002, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/66389.