Branch-and-bound algorithms for scheduling in an m-machine permutation flowshop with a single objective and with multiple objectives

N. Madhushini and Chandrasekharan Rajendran

European Journal of Industrial Engineering, 2011, vol. 5, issue 4, 361-387

Abstract: This paper presents branch-and-bound algorithms developed for an m-machine permutation flowshop to minimise the maximum weighted flowtime/maximum weighted tardiness/maximum sum of weighted flowtime and weighted tardiness/maximum sum of weighted flowtime, weighted tardiness and weighted earliness of a job, where each of the objectives is considered separately. A job-based bound, integrated with a machine-based bound, on the completion time of every unscheduled job by considering each of these objectives is developed, and the overall lower bound on a given objective at a given node in the branching tree is obtained by solving a bottleneck assignment problem. The proposed algorithms are evaluated by solving problems of various sizes, and some of these branch-and-bound algorithms (with the consideration of the maximum flowtime/the maximum tardiness) are compared with the existing algorithms available in the literature. This paper also presents the development and computational performance evaluation of a multi-objective branch-and-bound algorithm which can handle various combinations of objectives involving the sum of/maximum weighted flowtime, weighted tardiness and weighted earliness of jobs. [Received: 16 November 2008; Revised: 31 July 2009; Accepted: 28 March 2010]

Keywords: permutation flow shops; branch-and-bound algorithm; weighted flowtime; weighted tardiness; weighted earliness; Pareto-optimal solutions; non-dominated solutions; lower bound; upper bound; bottleneck assignment. (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=42737 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:eujine:v:5:y:2011:i:4:p:361-387

Access Statistics for this article

More articles in European Journal of Industrial Engineering from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().