A branch and bound algorithm for a production scheduling problem in an assembly system under due date constraints

A branch and bound algorithm for a production scheduling problem in an assembly system under due date constraints

0.00 Avg rating0 Votes
Article ID: iaor2001677
Country: Netherlands
Volume: 123
Issue: 3
Start Page Number: 504
End Page Number: 518
Publication Date: Jun 2000
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: integer
Abstract:

This paper focuses on a production scheduling problem in a tree-tructured assembly system operating on a make-to-order basis. Due dates are considered as constraints in the problem, that is, tardiness is not allowed. The objective of the problem is to minimize holding costs of final product inventory as well as work-in-process inventory. A mixed integer linear programming model is given and a branch and bound (B&B) algorithm based on a Lagrangian relaxation method is developed. In the algorithm, a subgradient method is used for obtaining good lower bounds of subproblems (or partial solutions) while a Lagrangian heuristic is used for upper bounds. Results of computational experiments on randomly generated test problems showed that the B&B algorithm found optimal solutions of problems of moderate sizes in a reasonable amount of computation time.

Reviews

Required fields are marked *. Your email address will not be published.