A Hybrid Meta-Heuristic to Solve a Multi-Criteria HFS Problem

A Hybrid Meta-Heuristic to Solve a Multi-Criteria HFS Problem

Fatima Ghedjati, Safa Khalouli
Copyright: © 2013 |Pages: 23
DOI: 10.4018/978-1-4666-2086-5.ch009
OnDemand:
(Individual Chapters)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

In this chapter the authors address a hybrid flow shop scheduling problem considering the minimization of the makespan in addition to the sum of earliness and tardiness penalties. This problem is proven to be NP-hard, and consequently the development of heuristic and meta-heuristic approaches to solve it is well justified. So, to deal with this problem, the authors propose a method which consists on the one hand, on using a meta-heuristic based on ant colony optimization algorithm to generate feasible solutions and, on the other hand, on using an aggregation multi-criteria method based on fuzzy logic to assist the decision-maker to express his preferences according to the considered objective functions. The aggregation method uses the Choquet integral. This latter allows to take into account the interactions between the different criteria. Experiments based on randomly generated instances were conducted to test the effectiveness of the approach.
Chapter Preview
Top

Introduction

Scheduling problems are encountered at all levels and in all sectors of activity. Most scheduling problems are very difficult to solve ((Blazewicz, Ecker, Pesch, & Schmidt, 1996)and (Graham, Lawler, & Rinnooy Kan, 1979)). That’s why the majority of the problems addressed in scheduling are only evaluated by a single criterion (such as makespan, total tardiness, workloads of machines, etc) (T’kindt & Billaut, 2002). However, in the literature, many researches in scheduling show that the majority of combinatorial optimization problems and especially the industrial ones involve generally simultaneous incommensurable criteria, which they can sometimes be contradictory. The combining of several criteria induces additional complexity. Optimizing multi-criteria problems seeks to optimize several components of a vector cost function (Talbi, 1999). Unlike single criterion optimization problems, there is no single optimal solution for multi-criteria problems, but a set of compromises solutions, known as Pareto-optimal solutions. These solutions are optimal in the wider sense that no other solutions in search space are superior to them when all criteria are considered (Zitzler & Thiele, 1999).

The hybrid flow shop (HFS), also called multiprocessor or flow shop with parallel machines, consists of a set of two or more processing stages (or centers) with at least one stage having two or more parallel machines. The hybrid characteristic of a flow shop is ubiquitously found in various industries. The duplication of the number of machines in some stages can introduce additional flexibility, increase the overall capacities, and avoid bottlenecks if some operations are too long. So, scheduling in HFS has a great importance from both theoretical and practical view points.

The main goal of this chapter is to present a solution methodology for solving a multi-criteria HFS problem. The considered objective is to simultaneously minimize the following criteria:

  • 1.

    Minimize the completion date of all the jobs (makespan),

  • 2.

    Minimize the weighted sum of the earliness and tardiness (ET) penalties.

Complete Chapter List

Search this Book:
Reset