| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 2.29 MB | Adobe PDF |
Orientador(es)
Resumo(s)
[Introduction] Since Davis [4] proposed the first Genetic Algorithm(GA) to address scheduling problems in 1985, GAs
have been widely used in manufacturing scheduling applications. However, most of the works deal with
optimisation of the scheduling problem in static environments, whereas many real world problems are
dynamic, frequently subject. to several sorts of random occurrences and perturbations, such as random
job releases, machine breakdowns, jobs cancellation and due date and time processing changes.
Due to their dynamic nature, real scheduling problems have an additional complexity in relation
to static ones. In many situations these problems, even for apparently simple situations, are hard to
solve, i.e. the time required to compute an optimal solution increases exponentially with the size of the
problem [1]. GAs have been extensively used in the context of Job-Shop Scheduling Problems (JSSP).
If all jobs are known before processing starts the JSSP is called static, while if job release times are not
fixed at a single point in time, ie. jobs arrive to the system at different times, the problem is called
dynamic. Scheduling problems can also be classified as deterministic, when processing times and all
other parameters are known and fixed, and stochastic, when some or all parameters are uncertain [7].
The proposed approach deals with these two cases of dynamic scheduling: deterministic and stochastic.
For such class of problems, the goal is no longer to find a single optimum, but rather to continuously
adapt the solution to the changing environment. The purpose of this paper is to describe an approach
based on GA for solving dynamic scheduling problems, where the products (jobs) to be processed have
due dates. This paper starts by presenting a scheduling system, based on Genetic Algorithms for the
resolution of the dynamic version of Single Machine Scheduling Problem (SMSP). The approach used
adapts the resolution of the static problem to the dynamic one in which changes may occur continually.
This takes into account dynamic occurrences in a system and adapts the current population to a new
regenerated population. Then, it is proposed an approach for the resolution of the Job-Shop Scheduling
Problem (JSSP) in dynamic environments.
The paper is structured as follows: section 2 provides a description of the considered scheduling problem. Section 3 summarises an approach for the resolution of the Dynamic Single Machine Scheduling
Problem. The proposed approach for dynamic scheduling is presented in section 4. Finally, the paper concludes with a summary and some ideas for future work.
Descrição
Palavras-chave
Contexto Educativo
Citação
Madureira, A., Ramos, C. & Silva, S. C. (2001, July 16-20). A genetic approach for dynamic job-shop scheduling problems.[Conference paper] 4th Metaheuristics International Conference - MIC'2001. Porto, Portugal