A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem

Date

2003-02-01

Author

Tozkapan, A
Kirca, O
Chung, CS

Metadata

Show full item record

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

Item Usage Stats

166
views

0
downloads

In this paper, a two-stage assembly scheduling problem is considered with the objective of minimizing the total weighted flowtime. A lower bounding procedure and a dominance criterion are developed and incorporated into a branch and bound procedure. A heuristic procedure is also used to derive an initial upper bound. Computational results of the algorithm are presented.

Subject Keywords

Scheduling, Two-stage assembly flowshop, Branch and bound algorithm, Total weighted flowtime

URI

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

Journal

COMPUTERS & OPERATIONS RESEARCH

DOI

https://doi.org/10.1016/s0305-0548(01)00098-3

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

A stochastic programming approach to the single machine makespan problem with random breakdowns Gürel, Tarık; Azizoğlu, Meral; Batun, Sakine; Department of Industrial Engineering (2022-12) In this thesis, we consider a single machine scheduling problem with random breakdowns. There is a single breakdown whose occurrence times follow a discrete distribution with known probabilities. We aim to minimize the expected makespan and propose a stochastic programming approach. We propose two stage stochastic programming models and a branch and bound algorithm. We enhance the performance of the branch and bound algorithm with an efficient branching scheme and powerful lower bounds. The results of ...
A simulated annealing approach to bicriteria scheduling problems on a single machine Karasakal, Esra (2000-08-01) In this paper, we apply a simulated annealing approach to two bicriteria scheduling problems on a single machine. The first problem is the strongly NP-hard problem of minimizing total flowtime and maximum earliness. The second one is the NP-hard problem of minimizing total flowtime and number of tardy jobs. We experiment on different neighbourhood structures as well as other parameters of the simulated annealing approach to improve its performance. Our computational experiments show that the developed appro...
A branch and bound method for the line balancing problem in U-shaped assembly lines with equipment requirements Ogan, Dilek; Azizoğlu, Meral (2015-07-01) In this study we consider a U-shaped assembly line balancing problem where each task uses a specified set of equipments and each type of equipment has a specified cost. Our problem is to assign the tasks together with their equipments to the workstations so as to minimize the total equipment cost. We formulate the problem as a mixed integer linear programming model that is capable of solving small sized instances. We propose a branch and bound algorithm that uses efficient precedence relations and lower bou...
A Branch and Bound Algorithm for a Multi-Mode Project Scheduling Problem With a Single Non-Renewable Resource Altıntaş, Cansu; Azizoğlu, Meral (2020-04-01) In this paper, a project scheduling problem with multi-modes and a single non-renewable resource is considered. The resource is released in pre-specified times at pre-specified quantities. An activity can be executed at different modes where a mode is defined by a processing time and a resource requirement amount. The objective is to minimize the project completion time. A branch and bound algorithm that enumerates the partial solutions based on the mode assignment decisions is presented. The results of the...
On the minimization of total weighted flow time with identical and uniform parallel machines Azizoğlu, Meral (1999-02-16) We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total weighted flow time. We discuss the properties that characterize the structure of an optimal solution, present a lower bound and propose a branch and bound algorithm. The algorithm is superior to prior methods presented in the literature. We also extend the algorithm to uniform parallel machines and solve medium-sized problem instances.

Citation Formats

A. Tozkapan, O. Kirca, and C. Chung, “A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem,” COMPUTERS & OPERATIONS RESEARCH, pp. 309–320, 2003, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/67319.