Percorrer por data de Publicação, começado por "2001-07-20"
A mostrar 1 - 3 de 3
Resultados por página
Opções de ordenação
- A Parallel Architecture for Solving Constraint Satisfaction ProblemsPublication . Mendes, Rui; Pereira, Jorge R.; Neves, José[Introduction] Real world problems can often be described by a set of constraints to be satisfied, where the goal is to find a feasible solution for the problem. The use of constraints allows one to model a wide variety of problems in a straightforward manner. However, finding a solution that either satisfies all constraints or maximizes some benefit is usually difficult, as existing algorithms for both problems are NP-hard. Furthermore, it is not always possible to satisfy all the constraints. In such cases, the goal is to find a solution that satisfies the maximum number of constraints (MMAX-CSPs) or one that satisfies the most important ones (MAX-WCSPs, where each constraint has a weight). Currently, local search is widely used to tackle these difficult problems. However, those methods are usually incomplete (i.e., they do not guarantee the optimum), and are often mislead by local optima. This situation is usually handled by restarting the search from another starting point. It is our goal in this paper to present a parallel architecture for solving constraint satisfaction problems (AntCSP); i.e., a parallel architecture that combines the stigmergetic capabilities of Ant Colony Optimization (ACO) metaheuristics, with local search heuristics to solve MANX-CSPs and Constraint Satisfaction and Optimization Problems (CSOPs). One of the main advantages of this approach is that no auxiliary structure is needed. The structure followed by the ants is the proof tree itself, in which the pheromones are laid. This not. only provides a very efficient implementation of pheromone updating but also a more general approach to solve CSPs. The other advantage is the use of parallelism both to have a number of ant colonies running in parallel and to have function distribution of local search procedures. This architecture thus provides a powerful tool to tackle these difficult problems by using available processing power.
- Influence of Solution Coding on Solving the Unit Commitment Problem with MetaheuristicsPublication . Viana, Ana; Sousa, Jorge P.; Matos, Manuel A.[Introduction excerpt] In Power Systems Engineering, as well as in many other areas of Electrical Engineering, optimising the usage of resources, subject to several constraints, is extremely important and usually difficult, due to specific technical, economical, or other particular aspects of the problem. The unit commitment problem is an important scheduling problem in planning the operation of power generators, and it is a good example of the interest devoted by the Power Engineering sector, to this area of research. It is the on/off decision problem of selecting the power generating units to be in service within a given planning horizon (from 1 day to 2 weeks, generally split in periods of 1 hour) and for how long. The committed units must satisfy the forecasted system load and reserve requirements, at minimum operating cost, subject to a large set of other system, technological and environmental constraints. Due to important start-up and shut-down costs, the problem is in general very hard to solve, as it is not possible to perform a separate optimization for each time interval. Furthermore, given that the operating costs depend on the load assigned to each generator, the problem of committing units over the planning horizon is directly connected to the additional problem of (roughly) assigning the load demand to the on-line units (“pre-dispatch” problem). The final, actual assignment is done later, for a much shorter period (usually from 15 to 60 minutes).
- A genetic approach for dynamic job-shop scheduling problemsPublication . Madureira, Ana Maria; Ramos, Carlos; Silva, Sílvio do Carmo[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.