A Genetic Algorithm for the Parallel Machine Scheduling Problem with Consumable Resources

A Genetic Algorithm for the Parallel Machine Scheduling Problem with Consumable Resources

Fayçal Belkaid (Manufacturing Engineering Laboratory of Tlemcen, University of Tlemcen, Tlemcen, Algeria), Zaki Sari (Manufacturing Engineering Laboratory of Tlemcen, University of Tlemcen, Tlemcen, Algeria) and Mehdi Souier (Manufacturing Engineering Laboratory of Tlemcen, University of Tlemcen, Tlemcen, Algeria, & Tlemcen Preparatory School of Economics, Tlemcen, Algeria)
Copyright: © 2013 |Pages: 14
DOI: 10.4018/jamc.2013040102


In this paper, the authors’ interest is focused on the scheduling problem on identical parallel machines with consumable resources in order to minimize the makespan criterion. Each job consumes several components which arrive at different times. The arrival of each component is represented by a curve-shaped staircase. This problem is NP-hard, further, there are not universal methods making it possible to solve all the cases effectively, especially for medium or large instances. A genetic algorithm is proposed to solve this problem due to proven great performance in solving combinatorial optimization problems. To check its effectiveness this algorithm is compared with an exact resolution method which enumerates all possible solutions for small instances and with a heuristic for large instances. Various randomly generated instances, which can represent realistic situations, are tested. The computation results show that this algorithm outperforms heuristic procedure and is tailored for larger scale problems.
Article Preview


During the past decades scheduling has been among the most studied optimization problems. Scheduling is a very current activity in industry. It optimizes the organization of workshops and it is a way to increase the profitability of manufacturing and production systems. It consists in allocating resources to tasks in time under several constraints. Its goal is to maximize (or minimize) different criteria as makespan, earliness/tardiness, etc. Thus, different scheduling problems are presented in the literature. Among these scheduling problems we can cite single and parallel machine scheduling, flow shop, job shop, etc.

In an industrial context, the presence of parallel or identical machines provides multiple alternate routes to produce a set of parts efficiently and with an ability to handle breakdowns and to continue producing the given set of part types. This family of system represents an important research field and it is widely studied in the literature. This problem is quite common in certain industries (textiles, in particular). It consists in assigning jobs to machines and determines the sequence of the jobs assigned to the same machine.

Parallel machines scheduling problem has been addressed in the context of several works for various criteria and different constraints and there are a variety of complex configurations that can be reduced to this type of problem. We can orient the reader to Chen et al. (1998); Mokotoff (2001); Allahverdi et al. (2008).

Parallel machine scheduling problems with the presence of consumable resources are very typical in industrial production practice and have wide application background in textile industry, shoes industry, electronic industry and so on. Whereas, a significant part of scheduling problems assume the total availability of resources, however, it is not always the case, resources can be consumed and may be unavailable for various reasons (as in production systems, the raw material is consumed at the completion of each task) and therefore, the unavailability of resources, disrupts and affects the efficiency of scheduling.

Therefore, in manufacturing system, there are many difficulties encountered through the scheduling because several parameters and constraints can be considered under various perturbations. Nevertheless, scheduling problems are relatively complex and therefore it is so difficult to solve all the cases optimally, in reasonable time (Garey & Johson, 1979).

As optimization techniques, metaheuristics represent an alternative way to solve complex optimization problems and to provide good solutions in acceptable time through the reduction of the explored space. Genetic algorithms are population based metaheuristics, proposed by Holland in 1975 (Holland, 1975). The basic concept of GAs is designed to simulate processes in natural system necessary for evolution, specifically those that follow the principles first laid down by Charles Darwin of survival of the fittest. This technique has been applied for solving several hard combinatorial optimization problems, the literature contains many papers like (Chaudhry & Drake, 2008; Zhang et al., 2011; Souier et al., 2013).

The objective of this paper is to implement a genetic algorithm which is the most common kind of metaheuristics for scheduling a set of jobs on identical parallel machines with consumable resources to minimize the makespan.

The remainder of this paper is organized as follows. The second section gives the literature review about the scheduling problems with consumable resource. The third section describes our problem. The fourth section is devoted to develop a genetic algorithm for solving the considered problem and to illustrate the allocated heuristic. In the fifth section, numerical computational results of different scale problems are reported. Finally, the last section concludes the work.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): Forthcoming, Available for Pre-Order
Volume 10: 4 Issues (2019): 2 Released, 2 Forthcoming
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing