Pure and Hybrid Metaheuristics for the Response Time Variability Problem

Pure and Hybrid Metaheuristics for the Response Time Variability Problem

Alberto García-Villoria (Institute of Industrial and Control Engineering (IOC), Universitat Politècnica de Catalunya (UPC), Spain), Albert Corominas (Institute of Industrial and Control Engineering (IOC), Universitat Politècnica de Catalunya (UPC), Spain) and Rafael Pastor (Institute of Industrial and Control Engineering (IOC), Universitat Politècnica de Catalunya (UPC), Spain)
DOI: 10.4018/978-1-4666-2086-5.ch010
OnDemand PDF Download:
No Current Special Offers


Metaheuristics are a powerful tool for solving hard optimisation problems. Moreover, metaheuristic hybrid optimisation techniques can be applied to develop an improved metaheuristic algorithm for a given problem. It is known that some metaheuristics perform better than others for each problem. However, there is a lack of theoretical basis to explain why a metaheuristic performs well (or bad) when solving a problem, and there is not a general guide to design specific hybrid metaheuristics. In this chapter, the authors describe the response time variability problem (RTVP), which is an NP-hard combinatorial optimisation problem that appears in a wide range of engineering and business applications. They show how to solve this problem by means of metaheuristics and how to design specific hybrid metaheuristics for the RTVP. This may be useful to managers, engineers, researchers, and scientists to deal with other types of optimisation problems.
Chapter Preview

1. Introduction

Since Toyota Motor Corporation popularized just-in-time (JIT) production systems, the problem of sequencing on mixed-model assembly lines has acquired high relevance. Mixed-model assembly lines are production lines that are able to produce small lots (ideally of size one) of different models with negligible costs when changing over one model to another. One of the most important JIT objectives is to get rid of all kinds of waste and inefficiency and, according to Toyota, the main waste is due to inventories. To reduce inventories, JIT production systems require producing only the necessary components in the necessary quantities at the necessary time. Because JIT is a pull production environment, the production schedule is focused on sequencing the models in the final assembly process.

The key to reduce inventories, as Monden (1983) says, is to have constant production rates and constant consumption rates of the components involved in the production process. First, the number of units of each model to be produced by the mixed-model assembly production line throughout the production period must be decided. Next, these units must be sequenced as regularly as possible. Regularity can be sought in the consumption of the components that arrive to the production line or in the production of the models that leave the production line. Depending on the kind of regularity desired, Kubiak (1993) classifies these sequencing problems into two categories, respectively: output rate variation (ORV) problems and production rate variation (PRV) problems.

The ORV problem concentrates on the consumption of the components needed by the models and its aim is to minimise the variations in this consumption in the production period. On the other hand, the PRV problem concentrates on the regularity of the models production. This kind of regularity is important when production needs to be adjusted to demand. Thus, according to the JIT system, it is possible to satisfy demands for a variety of models without holding large inventories or incurring large waits. Regularity in the PRV problem can be characterized in as many ways as discrepancy metrics are defined.

Miltenburg (1989) proposed four PRV metrics based on discrepancies between the real production rate and the ideal one (i.e., the one that would correspond to a constant rate of production). But other criteria can be use to measure the regularity or fairness of appearance of the models in the line (Bautista et al., 1997). For instance, Inman and Bulfin (1991) considered to minimise variations with respect to ideal production due dates for each unit.

The response time variability problem (RTVP) can be considered a PRV problem in the context of mixed-model assembly lines. The metric of the RTVP is based on the regularity, for each model, of the distances between the appearances of two consecutive units of that model. The application of the RTVP is not reduced into the mixed-model assembly lines context, but also includes, among others, computer multi-threaded systems, periodic machine maintenance, waste collection and scheduling of commercials.

It is well known that metaheuristic procedures are a good technique for solving real-life scheduling, combinatorial optimisation problems, as it is the RTVP. A lot of general metaheuristics have been proposed in the literature, from which we can choose the most suitable to solve our problem. However, we cannot usually know a priori which metaheuristic is the best to solve our particular variant of the problem. In this chapter, we show how we dealt with the solution of the RTVP in our studies by means of metaheuristics. We first show how the RTVP is solved by means of several types of metaheuristics following a methodology. This methodology helps us to see which characteristics or components may help to the metaheuristics to obtain good solutions. Then improved algorithms were developed based on new hybrid metaheuristics. It is shown that metaheuristic hybrid optimisation techniques are useful to improve the RTVP solution. We think that the steps that we followed are extendable when dealing other types of real world combinatorial optimisation problems.

The chapter is organized as follows. Section 2 describes the RTVP and explains real-life contexts in which may appear. The metaheuristics for the RTVP that we used, the followed methodology and the results of a computational experiment are shown in Section 3. Section 4 is dedicated to explain the design of the hybrid algorithms together with the results of the conducted computational experiment. Concluding remarks are given in Section 5.

Complete Chapter List

Search this Book: