Header menu link for other important links
X
Branch-and-bound algorithms for scheduling in an m-machine permutation flowshop with a single objective and with multiple objectives
Published in
2011
Volume: 5
   
Issue: 4
Pages: 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. Copyright © 2011 Inderscience Enterprises Ltd.
About the journal
JournalEuropean Journal of Industrial Engineering
ISSN17515254
Open AccessNo
Concepts (11)
  •  related image
    Branch-and-bound algorithms
  •  related image
    Lower bounds
  •  related image
    Nondominated solutions
  •  related image
    Pareto optimal solutions
  •  related image
    PERMUTATION FLOW SHOPS
  •  related image
    WEIGHTED EARLINESS
  •  related image
    WEIGHTED FLOWTIME
  •  related image
    WEIGHTED TARDINESS
  •  related image
    Branch and bound method
  •  related image
    Multiobjective optimization
  •  related image
    Scheduling algorithms