Metaheuristics for Production Scheduling E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 742

Veröffentlichungsjahr: 2013

Beschreibung

This book describes the potentialities of metaheuristics for solving production scheduling problems and the relationship between these two fields.

For the past several years, there has been an increasing interest in using metaheuristic methods to solve scheduling problems. The main reasons for this are that such problems are generally hard to solve to optimality, as well as the fact that metaheuristics provide very good solutions in a reasonable time. The first part of the book presents eight applications of metaheuristics for solving various mono-objective scheduling problems. The second part is itself split into two, the first section being devoted to five multi-objective problems to which metaheuristics are adapted, while the second tackles various transportation problems related to the organization of production systems.

Many real-world applications are presented by the authors, making this an invaluable resource for researchers and students in engineering, economics, mathematics and computer science.

Leseprobe

Table of Contents

Introduction and Presentation

I.1. Production scheduling

I.2. Metaheuristics

I.3. Applications of metaheuristics for solving monocriterion scheduling problems

I.4. Multicriteria scheduling problems

I.5. Scheduling transport problems

Chapter 1: An Estimation of Distribution Algorithm for Solving Flow Shop Scheduling Problems with Sequence-dependent Family Setup Times

1.1. Introduction

1.2. Mathematical formulation

1.3. Estimation of distribution algorithms

1.4. The proposed estimation of distribution algorithm

1.5. Iterated local search algorithm

1.6. Experimental results

1.7. Conclusion

1.8. Bibliography

Chapter 2: Genetic Algorithms for Solving Flexible Job Shop Scheduling Problems

2.1. Introduction

2.2. Flexible job shop scheduling problems

2.3. Genetic algorithms for some related sub-problems

2.4. Genetic algorithms for the flexible job shop problem

2.5. Comparison of codings

2.6. Conclusion

2.7. Bibliography

Chapter 3: A Hybrid GRASP-Differential Evolution Algorithm for Solving Flow Shop Scheduling Problems with No-Wait Constraints

3.1. Introduction

3.2. Overview of the literature

3.3. Description of the problem

3.4. GRASP

3.5. Differential evolution

3.6. Iterative local search

3.7. Overview of the NEW-GRASP-DE algorithm

3.8. Experimental results

3.9. Conclusion

3.10. Bibliography

Chapter 4: A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags

4.1. Introduction

4.2. Description of the problem

4.3. The proposed metaheuristics

4.4. Tests

4.5. Conclusion

4.6. Bibliography

Chapter 5: Neutrality in Flow Shop Scheduling Problems: Landscape Structure and Local Search

5.1. Introduction

5.2. Neutrality in a combinatorial optimization problem

5.3. Study of neutrality in the flow shop problem

5.4. Local search exploiting neutrality to solve the flow shop problem

5.5. Conclusion

5.6. Bibliography

Chapter 6: Evolutionary Metaheuristic Based on Genetic Algorithm: Application to Hybrid Flow Shop Problem with Availability Constraints

6.1. Introduction

6.2. Overview of the literature

6.3. Overview of the problem and notations used

6.4. Mathematical formulations

6.5. A genetic algorithm: model and methodology

6.6. Verification and validation of the genetic algorithm

6.7. Conclusion

6.8. Bibliography

Chapter 7: Models and Methods in Graph Coloration for Various Production Problems

7.1. Introduction

7.2. Minimizing the makespan

7.3. Maximizing the number of completed tasks

7.4. Precedence constraints

7.5. Incompatibility costs

7.6. Conclusion

7.7. Bibliography

Chapter 8: Mathematical Programming and Heuristics for Scheduling Problems with Early and Tardy Penalties

8.1. Introduction

8.2. Properties and particular cases

8.3. Mathematical models

8.4. Heuristics

8.5. Metaheuristics

8.6. Conclusion

8.7. Acknowledgments

8.8. Bibliography

Chapter 9: Metaheuristics for Biobjective Flow Shop Scheduling

9.1. Introduction

9.2. Metaheuristics for multiobjective combinatorial optimization

9.3. Multiobjective flow shop scheduling problems

9.4. Application to the biobjective flow shop

9.5. Conclusion

9.6. Bibliography

Chapter 10: Pareto Solution Strategies for the Industrial Car Sequencing Problem

10.1. Introduction

10.2. Industrial car sequencing problem

10.3. Pareto strategies for solving the CSP

10.4. Numerical experiments

10.5. Results and discussion

10.6. Conclusion

10.7. Bibliography

Chapter 11: Multi-Objective Metaheuristics for the Joint Scheduling of Production and Maintenance

11.1. Introduction

11.2. State of the art on the joint problem

11.3. Integrated modeling of the joint problem

11.4. Concepts of multi-objective optimization

11.5. The particle swarm optimization method

11.6. Implementation of MOPSO algorithms

11.7. Experimental results

11.8. Conclusion

11.9. Bibliography

Chapter 12: Optimization via a Genetic Algorithm Parametrizing the AHP Method for Multicriteria Workshop Scheduling

12.1. Introduction

12.2. Methods for solving multicriteria scheduling

12.3. Presentation of the AHP method

12.4. Evaluation of metaheuristics for the configuration of AHP

12.5. Choice of metaheuristic

12.6. AHP optimization by a genetic algorithm

12.7. Evaluation of G-AHP

12.8. Conclusions

12.9. Bibliography

Chapter 13: A Multicriteria Genetic Algorithm for the Resource-constrained Task Scheduling Problem

14.1. Introduction

13.2. Description and formulation of the problem

13.3. Literature review

13.4. A multicriteria genetic algorithm for the MMSAP

13.5. Experimental study

13.6. Conclusion

13.7. Bibliography

Chapter 14: Metaheuristics for the Solution of Vehicle Routing Problems in a Dynamic Context

14.1. Introduction

14.2. Dynamic vehicle route management

14.3. Platform for the solution of the DVRPTW

14.4. Treating uncertainties in the orders

14.5. Treatment of traffic information

14.6. Conclusion

14.7. Bibliography

Chapter 15: Combination of a Metaheuristic and a Simulation Model for the Scheduling of Resource-constrained Transport Activities

15.1. Knowledge model

15.2. Solution procedure

15.3. Proposed approach

15.4. Implementation and results

15.5. Conclusion

15.6. Bibliography

Chapter 16: Vehicle Routing Problems with Scheduling Constraints

16.1. Introduction

16.2. Definition, complexity and classification

16.3. Time-constrained vehicle routing problems

16.4. Vehicle routing problems with resource availability constraints

16.5. Conclusion

16.6. Bibliography

Chapter 17: Metaheuristics for Job Shop Scheduling with Transportation

17.1. General flexible job shop scheduling problems

17.2. State of the art on job shop scheduling with transportation resources

17.3. GTSB procedure

17.4. Conclusion

17.5. Bibliography

List of Authors

Index

First published 2013 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK

www.iste.co.uk

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA

www.wiley.com

© ISTE Ltd 2013

The rights of Bassem Jarboui, Patrick Siarry and Jacques Teghem to be identified as the author of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2013936302

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN: 978-1-84821-497-2

Introduction and Presentation

This book aims to underline the potentiality of metaheuristics for solving production scheduling problems.

To help the reader, the chapters have been presented under the following three topics: applications of metaheuristics for solving monocriterion scheduling problems; multicriteria scheduling problems; and scheduling transport problems.

I.1. Production scheduling

Production scheduling in manufacturing is continually assessed in order to produce high-quality and reliable goods without time delays. To fulfill these objectives, manufacturers currently rely on a number of tools such as scheduling, which is one of the most important factors for planning operations in manufacturing production systems. Scheduling is also used for both human and technology resources to satisfy clients’ demands and production schedules set out by company planning departments. This function must organize the simultaneous execution of several activities while accounting for constraints on available resources. Depending on the situation, resources and activities may take different forms. For example, resources may include machines on an assembly floor, nurses and operating rooms in a hospital, truck drivers, computer programs, etc., while activities or jobs may be operations in a manufacturing process, patients in a hospital, deliveries or tasks to be executed by a computer program, etc. A number of measures of performance are used to optimize schedules. For instance, an objective may include minimizing the time taken to complete a series of jobs while another may be reducing average sojourn time or even minimizing the number of jobs completed after their target completion dates.

Scheduling jobs is an important activity for maintaining firms’ competitive positions. The problem involves setting out the order in which a number of jobs must be executed on a series of highly specialized machines as well as their resource needs such that one or several objectives are optimized. To formulate a scheduling problem, we need specific information relating to the sets of jobs, machines, the range of resources and the performance criteria during the optimization phase.

A job can be described according to a series of characteristics: resource needs, duration of processing, time at which it begins and time at which it completes. In general, the duration of a job is uncertain, but to simplify the solution we can remove this uncertainty from the problem’s statement. It must also describe the technological constraints (priority restrictions) that exist between jobs.

Machines can take two forms: those that can execute all jobs (known as parallel machines) and those that are specialized in executing a subset of jobs (known as specialized machines).

Industrial scheduling problems have a structure that contains a set of jobs to be carried out and a set of available resources to complete these jobs. There are several types of resources, which include:

– Renewable resources, where we have a constant quantity of resource units during each period, which are continually available. These resources may be workers, machines, etc.

– Non-renewable resources, where we have a limited number of resources across the year. These resources may include a budget, raw materials, etc. The problem of using non-renewable resources only arises when there are several modes of execution, that is when each job needs to be carried out differently, thereby influencing the consumption of resources and duration of execution.

In a scheduling problem, we want to optimize one or several criteria at the same time. The most commonly used criteria include:

– The minimization of the total schedule duration (the makespan): this criterion generally indicates machines’ correct use.

– The total weighted flow time: this criterion aims to minimize clients’ waiting time according to their importance or even minimize product storage costs during production.

– Total weighted tardiness: this criterion measures the cost of delay that is a function of the length of delay multiplied by the cost of delay associated with each job.

– The number of tardy jobs: this criterion measures the number of times delays are not respected.

– Weighted earliness and tardiness: this criterion measures the cost of earliness and delays with regard to their costs. In general, the cost on early completion is relative to the cost of storing the final product.

I.2. Metaheuristics

Scheduling has been intensively studied for over 50 years. This field has drawn the attention of researchers specializing in management, industrial engineering, operational research and computing. It has been shown that correct scheduling is an extremely difficult job. Standard operational research approaches such as mixed integer linear programming or dynamic programming are often of limited use due to their excessive computation time. As a result, heuristic solution methods have been proposed, which provide good solutions with a reasonable computation time. However, these methods have two significant disadvantages. First, they are adapted to a specific problem and they are difficult, if not impossible to adapt to other problems. Second, they are generally designed to “construct” a unique solution while the majority of decision problems have a large number of feasible solutions. It is for this reason that there is a higher probability of there being better solutions. To overcome these shortcomings, independent problem research strategies, specifically metaheuristics, have been proposed.

For a number of years, solution methods for scheduling problems based on metaheuristic approaches have seen a large degree of success that is explained by their ability to provide solutions close to the optimum within a reasonable time.

The term metaheuristics relates to general heuristics that can be easily adapted to a highly varied class of optimization problems. Beyond this varied use and relatively simple implementation, the principle advantage of metaheuristics is that it is capable, in contrast to the majority of standard heuristics, of avoiding being blocked in a local optimum of the function being optimized and therefore approaches a global optimum of this. Over the past 30 years, a number of metaheuristics have been proposed, of which there are two main types of method:

– Local search methods that, on the basis of a current solution, explore its neighborhood to determine a new one. The most commonly known metaheuristics in this category include simulated annealing, tabu search as well as greedy randomized adaptive search procedure (GRASP), variable neighborhood search (VNS) and iterated local search (ILS).

– Evolutionary methods that cause a family of solutions to evolve at each iteration. The genetic algorithm is a basic method in this category, although there are a number of other algorithms such as the ant colony algorithm.

I.3. Applications of metaheuristics for solving monocriterion scheduling problems

The first part of this book focuses on several applications of metaheuristics for solving monocriterion scheduling problems.

In Chapter 1, Mansour Eddaly, Bassem Jarboui, Radhouan Bouabda, Patrick Siarry and Abdelwaheb Rebaï examine a flow shop scheduling problem with families of jobs and with a setup time depending on the sequence of families. This problem may be defined as follows. We identify a series of families of jobs that must be scheduled on a series of machines with the same order of execution on all the machines. The aim is to find the sequence of families as well as sequence of jobs that minimize the schedule’s total duration. Given that this problem is NP-hard, this chapter proposes a metaheuristic approach based on the estimation of distribution algorithm. The authors have therefore developed a probabilist method that accounts for both the significance of the order of jobs in their sequences and the importance of similar blocks in sequences. They then propose a hybridization with the iterated local search algorithm to reinforce the intensification mechanism.

In Chapter 2, Imed Kacem summarizes the main approaches to solving flexible job shop scheduling problems. This is an extension of the standard job shop problem that allows an operation to be executed on a series of machines with varying performances. This entails allocating a machine for each operation and then scheduling them such that the maximum execution time for all operations (the makespan) is minimized. This chapter describes the main developments achieved using genetic algorithms and provides a comparative analysis of the main codings and operators.

In Chapter 3, Hanen Akrout, Bassem Jarboui, Patrick Siarry and Abdelwaheb Rebaï consider the flow shop scheduling problem without waiting time. This problem involves scheduling a finite number of jobs on several machines in the same order. The job’s execution start time on the first machine must be delayed in order to ensure that the job is scheduled on the factory floor without waiting time on any machine. The aim is to minimize the total duration of all the jobs’ schedules. To solve this problem, the authors propose incorporating the differential evolution algorithm into the GRASP method to improve its operation. The success of GRASP depends on the choice of parameter that limits the set of elements in the Restricted Candidate List (RCL). The adjustment of this parameter is therefore considered to be a major disadvantage of the GRASP method since it defines this parameter as a constant for all instances during the construction of a single solution. It is for this reason that the authors propose an auto adjustment of this parameter that must be able to adapt from one scenario to another during the construction of a solution. In addition, the authors have used an iterative local search algorithm based on four neighborhood structures to improve the GRASP method.

Chapter 4, edited by Emna Dhouib, Daniel Tuyttens, Jacques Teghem and Taïcir Loukil, examines the problem of flow shop permutation when there are time-lag constraints. Time-lags are defined as being time intervals between each pair of successive operations of the same job. The objective is to minimize two criteria hierarchically: the first is the number of tardy jobs and the second is the makespan. Two metaheuristics are proposed to solve this problem: the first being a variant of the simulated annealing algorithm and the second is the GRASP algorithm. These two approaches are evaluated and experimentally compared using a number of varied and randomly generated instances.

Chapter 5, edited by Marie-Eléonore Marmion, focuses on neutrality in the permutation flow shop problem. The concept of neutrality relates to a search space that has several neighboring solutions with the same objective function value. After an overview of this subject, Marmion examines the main concepts and basic notions, followed by an analysis of neutrality in the flow shop problem. Finally, Marmion proposes an iterative local search approach that exploits the neutrality of neighborhood while authorizing neutral displacements to solve this problem.

In Chapter 6, Nadia Chaaben, Racem Mellouli and Faouzi Masmoudi consider the problem of production scheduling in a hybrid flow shop workspace in the presence of different periods of machine unavailability due to preventative maintenance as well as different goods availability (or arrival) dates. The aim is to minimize the schedule end date. The problem’s NP-hard nature means that the use of metaheuristic approaches to solve it seems highly justified. The authors have proposed a genetic algorithm based on a new chromosome coding model that has been specifically adapted to this type of manufacturing environment. The proposed algorithm’s performance is tested using small and large, randomly generated, instances. The exact solutions calculated using mathematical programming methods, which have been specifically developed for this problem, are compared in terms of the quality of their resulting bounds.

In Chapter 7, Nicolas Zufferey examines a variety of production scheduling problems on parallel machines with incompatibility constraints on specific pairs of jobs that cannot be carried out within the same time period. The author proposes solutions for three variants of this problem using coloring graph and metaheuristic models. The first problem entails maximizing the number of jobs carried out when the makespan is imposed and the second considers the existence of precedence constraints between jobs, while the third presents a relaxation of the initial problem by authorizing incompatible jobs during the same time period while supporting incompatibility constraints. Several metaheuristic applications are examined, including a tabu search, an ant colony algorithm, a variable neighborhood search algorithm and a genetic algorithm.

In Chapter 8, Mustapha Ratli, Rachid Benmansour, Rita Macedo, Saïd Hanafi and Christophe Wilbaut focus on the problem of scheduling jobs on a machine with earliness and tardiness penalties while all the jobs have a shared end date. After describing the general framework of machine scheduling with earliness and tardiness penalties and highlighting some of the important properties of the problem considered, they also examine several mathematical models of the problem. This is followed by a comparative study of all existing examples, which highlights the difficulty of solving average size instances with these models. The remainder of this chapter examines the methods used to effectively solve large-scale problems. After an examination and comparison of several constructive heuristics, the chapter examines the metaheuristics proposed for this problem. This chapter concludes by providing a new comparative study highlighting a level of quality that is relatively common with the majority of these approaches. Finally, several conclusions and suggestions are made for future research of this problem.

I.4. Multicriteria scheduling problems

This second part focuses on multicriteria scheduling problems.

Production scheduling lends itself very well to multicriteria optimization. This lies in the fact that, i.e. depending on the chosen optimization criterion, that is maximal completion time or makespan, average completion time, maximal total tardiness and number of tardy jobs, the optimum solution to a unicriterion model will be different. Indeed, each of these criteria has its own significance and it is therefore often important to consider several criteria simultaneously. In addition, criteria other than these standard criteria can also arise in specific situations such as the cost of rejecting a job, penalties for non-satisfaction of constraints or delays on an initial schedule.

In a multicriteria optimization problem, there is not a single “optimal solution” that optimizes all the criteria simultaneously. The objective is therefore to identify one, several or all the “efficient or optimal Pareto” solutions. A solution is deemed efficient if it is not dominated, that is that there is no other feasible solution that is as good for all criteria and even better for at least one criterion. The image of all the efficient solutions in the criteria space is known as the “Pareto Front”.

There are various possible approaches.

– The a priori approach is the approach where we optimize a criteria aggregation function. This function is provided by the decision-maker and is interactively constructed with her/him. A particular situation is one where criteria are rated in terms of a hierarchy of importance and that therefore, where there are two criteria among the optimum solutions for the most important criterion, we determine which optimizes the second criterion. In this approach, a single effective criterion is identified.

– The a posteriori approach entails determining all the efficient solutions and presenting them to the decisionmaker who can then choose between them. This commonly used approach is examined in all the chapters of part one, along with Chapter 12.

– The interactive approach involves the decisionmaker in the construction process for an efficient solution by asking her/him to react to the current solution from each iteration in order to search for a solution that better fits her/his preferences.

Multicriteria scheduling problems are specific examples of multicriteria combinatorial optimization problems that are generally NP-hard. In addition, when the size of this kind of problem exceeds a specific threshold, it is impossible to determine all the efficient solutions within a reasonable time frame. This explains the success of metaheuristic methods adapted to multicriteria optimization. These methods, whether local search, evolutionary or hybrid, have seen an extraordinary development over the past 20 years. The aim is therefore to determine a good approximation of all the efficient solutions. The retained solutions are often known as “potentially efficient”. One of the difficulties in this approach is comparing methods because the comparison of two approximations is in itself a multicriteria problem. To enable this comparison, there are various quality indicators. Nevertheless, it is prudent to carry out statistical tests before a meaningful solution can be drawn.

Chapter 9, by Matthieu Basseur and Arnaud Liefooghe, provides an excellent introduction to multicriteria scheduling by considering a biobjective flow shop problem with different pairs of standard scheduling criteria. An approximation of the Pareto front is determined using four multicriteria metaheuristics, two local search and two evolutionary-based metaheuristics. The obtained results are compared using a “hypervolume difference” quality indicator and the conclusions are validated by a statistical test, followed by a correlation study between the different objective functions.

Chapter 10, edited by Caroline Gagné, Arnaud Zinflou and Marc Gravel, examines a particularly interesting real-life application of production scheduling on a car manufacturing line. This real-life scenario has also been the focus of the 2005 ROADEF challenge, although the proposed problem consisted of hierarchically optimizing three criteria. Note that these three criteria are not standard but related to the specific problem being examined (changing the line’s paint color, two conflict types due to the assembly floor’s limited capacity). The ingenuity of this chapter is twofold:

– The scheduling problem is examined from a multicriteria perspective by determining an approximation of the Pareto front, thereby enabling a greater degree of flexibility in the decisionmaker’s choice.

– Two new algorithms are proposed, the first being a genetic algorithm and the second based on this hybridization with an artificial immune system.

The focus of Chapter 11, proposed by Ali Berrichi and Farouk Yalaoui, is the joint analysis of two types of functions that have generally been examined separately, despite their interdepence; the production schedule function, here on a parallel machine model, and the preventive maintenance function, in this case with a failure level and constant repair rate for each machine. The criteria considered with regard to the schedule are the total job delays and machine unavailability with regard to the maintenance. An original algorithm based on a particle swarm optimization algorithm but mixed with a local search method is proposed in order to approximate the Pareto front. This is concluded by a comparison with two multiobjective genetic algorithms from the literature using the “covering” quality indicator with conclusions being validated by statistical tests.

Chapter 12, by Fouzia Aounnar, Patrick Pujo and Afef Denguir, is more specific. On the one hand, they examine a project scheduling problem where jobs are connected by precedence constraints and may be carried out according to different modes and, on the other hand, different alternative solutions must be compared against multiple criteria. To do so, a multicriteria analysis method must be applied. The approach used is the Analytic Hierarchy Process (AHP) method that has a number of parameters. The authors propose a genetic algorithm to fix these parameters, which influence the final choice, as much as possible.

In Chapter 13, Olfa Dridi, Saoussen Krichen and Adel Guitouni examine a real-life application of a maritime surveillance system entailing protection, search and rescue operations to ensure the system’s safety. The problem is modeled using a job scheduling, multimodal and multiobjective resource allocation problem. To solve it, a genetic algorithm adapted to the model is proposed in order to approximate the Pareto front. Quality indicators are used to analyze the results that are validated by a statistical test.

I.5. Scheduling transport problems

This part is devoted to scheduling transport problems.

Scheduling in the transport industry raises a number of particularly difficult optimization problems. Metaheuristic solving techniques have seen a great amount of success because they are likely to provide high-quality solutions at an acceptable calculation cost. There are two main fields of applications: transport systems used to deliver and distribute goods or services and transport resources required on a factory floor, at different stages of the production process.

In the goods and service transportation industry, transport costs represent an increasing share in the final cost handed to the client. It is therefore essential to manage these costs throughout global logistics networks. One of the central problems in goods transportation is that of vehicle routing problems (VRP). This involves constructing itineraries such that a fleet of vehicles can visit, as cheaply as possible, from one or several depots, a series of clients. In the literature, the resolution of this NP-hard problem frequently relies on metaheuristics. The majority of research published has focused on static and determinist examples where all information is known in advance and is not subject to change throughout the whole planned cycle. However, in practical applications, unforeseen circumstances can arise while the planned itinerary is being executed. The transporter must therefore take these events into consideration to provide a greater quality of service and manage her/his fleet of vehicles more effectively.

In Chapter 14, the first chapter of this book to examine transport scheduling problems, Tienté Hsu, Gilles Gonçalves and Rémy Dupas propose a metaheuristic to solve VRP in a dynamic context. They have observed that, using technological advances in mobile communications and geolocalization, transporters can communicate with drivers and can instantly know the position and state of the cargo of each of its vehicles at any one time. However, not all information can be known in advance. For example, in the case of a fuel delivery, the quantity required by the client can only be known once the carrier is on site. This evolutionary context requires a rapid solution time. Indeed, the arrival of each new element renders the current solution partially obsolete. It is also important to react quickly to adapt the current solution to a new context or even, in addition, refine the obtained solution. The metaheuristic presented in this chapter allows us to specifically account for uncertainties in the quantities to be delivered and setbacks in journey times.

Chapter 15, written by Virginie André, Nathalie Grangeon and Sylvie Norre, examines a hospital context and a transport scheduling problem where there are resource constraints. The Clermont-Ferrand University Hospital is made up of a number of functional units that share buildings according to their medical (pediatry, maxillo-facial surgery, etc.) or technical speciality (buying, maintenance, production, etc.). Consumption sites are functional units that use products necessary for their activities and production sites are functional units responsible for allocating consumption units. A transport activity is defined by a production and consumption site and requires a driver and vehicle. In addition to vehicles and drivers, other resources such as production lines, loading bays and cleaning areas, with limited availability, must be taken into account before (preparation and loading) and after (unloading and cleaning) transport. Finally, the number of containers required for each product is limited. Andre, Grangeon and Norre have focused on identifying the numbers of drivers’ shifts, required to carry out all activities, and in addition, the schedule for these activities in order to respect precedence constraints, earliest availability dates and latest completion dates. To approach this application, which is essentially a pickup and delivery problem, they have combined a metaheuristic with a simulation model.

In Chapter 16, Rahma Lahyani, Frédéric Semet and Benoît Trouillet examine a specific type of VRP problem that integrates scheduling constraints in addition to the usual constraints. Their existence affects decisions relating to vehicles’ positions not only in terms of space but also of time. To solve these schedule constrained routing problems, several types of approaches have been proposed in the literature. First, exact approaches can even today only be used to solve instances of limited size. When we consider the most complex cases involving multiple constraints or where we face large-scale problems, heuristic approaches are required. Today, the so-called standard heuristics are no longer competitive, both in terms of their quality of solution and computation time. This chapter shows that more recent adaptations of metaheuristics respond to these two criteria. Several VRP variants are examined, emphasizing the differences between the basic and extended versions that jointly involve spatial and temporal scheduling decisions. The chapter specifically examines an example where the distribution of vehicles and work groups need to be optimized.

The final chapter, Chapter 17, written by Qiao Zhang, Hervé Manier and Marie-Ange Manier, focuses on resource transportation scheduling problems on factory floors. In production systems, optimization relates to the efficient use of resources such as processing resources, storage and transport resources involved at different stages of the manufacturing process. A normal approach entails scheduling all activities according to their operational range of products required. Standard scheduling problems involve finding an order and execution date for all jobs while optimizing a specific objective function under a given set of constraints. In this framework, transport constraints are often put aside. Nevertheless, in some factories, transport resources are genuinely critical and their associated parameters, such as the time taken to move product between two machines, can no longer be ignored. The authors have proposed a generic model for transport resource scheduling problems and have developed a hybrid metaheuristic, which allows us to effectively solve several types of problems.

Chapter written by Bassem JARBOUI, Patrick SIARRY and Jacques TEGHEM.

Chapter 1

An Estimation of Distribution Algorithm for Solving Flow Shop Scheduling Problems with Sequence-dependent Family Setup Times

1.1. Introduction

Since the 1960s, the development of cellular manufacturing systems (CMS) as a technology has drawn the attention of both researchers and manufacturers in the production system industry. Its principal focus is to reduce complexity and improve the output of production lines [GRE 84]. Operationally, the CMS entails arranging a set of similar jobs into part families. Their similarities concern job preparation time, machine requirements and necessary operations.

Several industrial applications can be included in CMS environments, such as the production of microchips, the manufacture of metal products and manual assembly industries [GRE 84]. Hendizadeh et al. [HEN 08] have provided an overview of CMS scheduling problems.

In this chapter, we will focus on a CMS scheduling problem while processing jobs with the same setup family together. Moreover, in each family, there is a set of n jobs that must be executed on a set of m machines following the same order of execution without preemption (no interruption is allowed). Such cells are known as flowline cells or pure flow shop manufacturing cells [SCH 00]. In practice, this problem arises when the scheduling time required for two jobs in the same family is restricted or included in the execution time. This problem occurs when the time required to shift from one part (job) to another is negligible or included in the processing times. However, the time required to shift from one family to another is high and cannot be ignored. Cheng et al. [CHE 00] have provided a comprehensive review for flow shop scheduling problems with setup times. They have classified the problem considered in this chapter in the category of scheduling problems with sequence-dependent family setup times (SDFST). Schaller et al. [SCH 00] have examined a real-world application in the manufacture of printing circuit boards where cell manufacturing systems are strongly required.

Garey and Johnson [GAR 79] have demonstrated that this problem is NP-hard if we minimize the maximum completion time (makespan). This justifies the use of approximate algorithms over exact methods for solving this problem. The use of approximation algorithms is recommended for solving this kind of problem. Schaller et al. [SCH 00] have proposed lower bounds on the makespan criterion in order to introduce them into a branch and bound algorithm. The obtained results have shown that the proposed algorithm appears effective for small-scale instances. Nevertheless, when the number of families or machines increases, the performance of lower bounds drops considerably. In addition, this piece of research also proposed several constructive heuristics. The experimental results for these heuristics have shown that Campbell et al.’s “CDS” heuristic [CAM 70] is the best suited for scheduling jobs in each family. Furthermore, the well-known NEH heuristic [NAW 83] appears to be the most appropriate for family sequencing. França et al. [FRA 05] have examined two evolutionary algorithms (EAs), including a genetic algorithm (GA) and a mimetic algorithm (MA). The results have shown the effectiveness of these two algorithms in relation to the approaches previously described in the literature. In addition, MA shows a slight superiority in relation to GA. Hendizadeh . [HEN 08] have employed concepts of the simulated annealing (SA) algorithm to create a balance between intensification and diversification in the search’s direction. The obtained experimental results have shown that the proposed algorithm provides a better quality of solution in relation to Schaller .’s [SCH 00] constructive heuristics in terms of solution quality but not in terms of Central Processing Unit (CPU) time. In addition, on average, Tabu Search (TS) and MA algorithms perform similarly. Lin [LIN 09] have proposed three metaheuristics such as SA, GA and TS to solve this problem. It should be noted that SA and GA algorithms perform better than França [FRA 05] MA and Hendizadeh [HEN 08] TS algorithms, both in terms of the quality of solution and execution time.