ISEP – DEI – Comunicações em eventos científicos
URI permanente para esta coleção:
Navegar
Entradas recentes
- A Genetic Algorithm for the Dynamic Single Machine Scheduling ProblemPublication . Silva, Sílvio do Carmo; Madureira, Ana Maria; Ramos, Carlos; Camarinha-Matos, Luís; Afsarmanesh, Hamideh; Erbe, Heinz-H.This paper starts by studying the performance of two interrelated genetic algorithms (GA) for the static Single Machine Scheduling Problem (SMSP). One is a single start GA, the other, called MetaGA, is a multi-start version GA. The performance is evaluated for total weighted tardiness, on the basis of the quality of scheduling solutions obtained for a limit on computation time. Then, a scheduling system, based on Genetic Algorithms is proposed, for the resolution of the dynamic version of the same problem. 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
- 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.
- 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.
- Abordagens ao Problema de Escalonamento em Ambientes Reais de ProduçãoPublication . Madureira, Ana Maria; Almeida, Ana[Resumo] Num sistema de fabrico do tipo Job-Shop podem ser identificados alguns factores que contribuem para a dificuldade do processo de escalonamento, nomeadamente, a complexidade, as restrições e a incerteza. Os ambientes industriais reais são sujeitos a várias fontes de mudança, as quais são tratadas como ocorrências aleatórias, tais como, lançamento de novas ordens de fabrico, avarias, alterações de prioridades, atrasos nas operações, etc. Por escalonamento dinâmico consideramos a situação na qual um plano flexível é executado, isto é, o plano inicial é dinamicamente ajustado (re-escalonado) sempre que eventos inesperados ocorrem no sistema. Esta comunicação tem por objectivo principal efectuar uma sistematização de conceitos e classificações de problemas e tipos de escalonamento, bem como das abordagens usadas na sua resolução. Inicialmente, é apresentado o problema de escalonamento, através da caracterização dos seus elementos e da referência a algumas definições encontradas na literatura, A seguir descrevem-se algumas classificações para os problemas de escalonamento e os tipos de abordagens de resolução a adoptar. Finalmente, são propostas duas arquitecturas para a resolução do problema de escalonamento em ambientes reais de produção caracterizados por um elevado grau de dinamismo. À primeira baseada em Sistemas de Apoio à Decisão e a segunda em Algoritmos Genéticos.
- Dynamic scheduling of manufacturing orders: A decision support system approachPublication . Almeida, Ana; Ramos, Carlos; Silva, S. D. C.This paper presents a decision support system (DSS) based architecture and a new method for the dynamic scheduling of manufacturing systems. The proposed architecture is based on the DSS paradigm. The typical scheduling problems, namely the order allocation and order sequencing problems, are to be solved for a given production plan which defines a set of manufacturing orders to be processed. These specify product types to be manufactured, their quantities and due dates. The allocation problem deals with the assignment of n orders to m manufacturing processors, under the given production plan, and the solution to the sequencing problem identifies the input sequence and the instants of processing of the assigned orders on each manufacturing processor.
- Decision support system for dynamic production schedulingPublication . Marinho, José; Ramos, Carlos; Bragança, AlexandreThis paper presents a system to support decision-making of the production manager when scheduling the manufacturing orders. This system is mainly appropriate for small and medium size enterprises with productive systems like batch or job-shop. The manufacturing orders are dynamically scheduled considering namely deadlines and resource allocation. The system combines three modules: pre-scheduling, dynamic scheduling and re-scheduling. Each module applies heuristics to select the best solutions depending on the scheduling policies defined by the production manager.
- Distributed task schedulingPublication . Sousa, Paulo; Ramos, CarlosProposes an architecture for manufacturing enterprises based on the holonic concept. The main advantage of this approach is the decentralised, distributed nature of the system as well as its heterarchic organisation as opposed to the rigid hierarchic and centralised nature of computer integrated manufacturing (CIM). The system models products, resources and tasks and the planning, scheduling and order management functions of the enterprise. A negotiation protocol is defined for task assignment that is an extension of the contract net protocol. The protocol is based on the task-resource abstraction and is suited for negotiation in several situations not only for the dynamic scheduling of manufacturing orders. The negotiation protocol is able to handle exceptions such as machine breakdowns and rush orders.
- Infrastructures and scheduling method for holonic manufacturing systemsPublication . Silva, Nuno; Ramos, CarlosManufacturing systems are changing structure and organisation. Supply chains are evolving to more coupled organisations like virtual enterprises, though maintaining the single entities autonomy, adaptability and dynamism properties. Such organisations imply organisational and technological shift through agility, distribution, decentralisation, reactivity and flexibility. New organisational and technological paradigms are needed in order to reply to the modern manufacturing systems challenges. The paper proposes and justifies the holonic manufacturing system concept as the main organisational paradigm presents the infrastructures needed to assure system operation, security, coherence and coordination. Additionally, the scheduling sub-system is presented along with a scheduling method developed as a case study.
- Multi-agent simulation for balancing of assembly linesPublication . Ramos, Carlos; Praça, IsabelOne of the main applications of simulation is in manufacturing systems. The complexity of this kind of systems is related to the number of decisions that must be taken in shorter time. The main difficulty is to predict the effects of decisions on the overall system performance. In this context simulation becomes an important tool by means of which it is possible to predict the future performance of the system, and so compare and analyse different decisions. The actual discrete-event simulation scenario reveals a systematic demand for more sophisticated and powerful computational tools in order to fulfil the increasing problem of complexity. Computer network technology provides the computational power needed. The combination of distributed simulation with that of multi-agent systems presents a very interesting perspective to design and develop such kinds of environments. We propose an architecture based on multi-agent simulation to help solving problems in balancing and distributing the human resources in manual assembly lines, and in the future we hope to extend the model to other kinds of manufacturing systems.
- CEPP: Conversion and execution of process plansPublication . Ramos, Carlos; Figueiredo, LinoThis paper deals with a method to produce a program in numerical control (NC) language from a part drawing in a CAD system. This method is applied to any piece with revolution axis that can be machined in a CNC lathe. The method was developed with the goal of being integrated in the control software of the flexible manufacturing system existent in the CIM center of ISEP. The proposed method involves three phases, which are presented and explained.