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

Tozkapan, A
Kirca, O
Chung, CS
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.


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.
An adaptive simulated annealing algorithm-based approach for assembly line balancing and a real-life case study
Guden, H.; Meral, Fatma Sedef (2016-05-01)
In this study, we address the deterministic assembly line balancing problem (ALBP) in a multiple product-models environment with multiple objectives. We have been motivated by the assembly line balancing problem of a white goods product production line that is a multi-model type line with 68 stations through which four product-models are assembled, each with approximately 400 precedence relations and 300 tasks. In the plant, to cope with the increasing demand in the medium term, the efficiency of the line i...
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.