Article Preview
TopIntroduction
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.