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

Authors: N. Madhushini; Chandrasekharan Rajendran

Addresses: Caterpillar Logistics Services India Pvt. Ltd., 1A 5th Floor, RMZ NXT Campus, Whitefield Main Road, Bangalore 560 066, India. ' Department of Management Studies, Indian Institute of Technology Madras, Chennai 600 036, India

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.

DOI: 10.1504/EJIE.2011.042737

European Journal of Industrial Engineering, 2011 Vol.5 No.4, pp.361 - 387

Published online: 22 Oct 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article