Constraint based methods for allocation and scheduling of periodic applications

This work presents exact algorithms for the Resource Allocation and Cyclic Scheduling Problems (RA&CSPs). Cyclic Scheduling Problems arise in a number of application areas, such as in hoist scheduling, mass production, compiler design (implementing scheduling loops on parallel architectures), software pipelining, and in embedded system design. The RA&CS problem concerns time and resource assignment to a set of activities, to be indefinitely repeated, subject to precedence and resource capacity constraints. In this work we present two constraint programming frameworks facing two different types of cyclic problems. In first instance, we consider the disjunctive RA&CSP, where the allocation problem considers unary resources. Instances are described through the Synchronous Data-flow (SDF) Model of Computation. The key problem of finding a maximum-throughput allocation and scheduling of Synchronous Data-Flow graphs onto a multi-core architecture is NP-hard and has been traditionally solved by means of heuristic (incomplete) algorithms. We propose an exact (complete) algorithm for the computation of a maximum-throughput mapping of applications specified as SDFG onto multi-core architectures. Results show that the approach can handle realistic instances in terms of size and complexity. Next, we tackle the Cyclic Resource-Constrained Scheduling Problem (i.e. CRCSP). We propose a Constraint Programming approach based on modular arithmetic: in particular, we introduce a modular precedence constraint and a global cumulative constraint along with their filtering algorithms. Many traditional approaches to cyclic scheduling operate by fixing the period value and then solving a linear problem in a generate-and-test fashion. Conversely, our technique is based on a non-linear model and tackles the problem as a whole: the period value is inferred from the scheduling decisions. The proposed approaches have been tested on a number of non-trivial synthetic instances and on a set of realistic industrial instances achieving good results on practical size problem.

Scheduling of continuous and discontinuous material flows with intermediate storage restrictions

This paper deals with scheduling batch (i.e., discontinuous), continuous, and semicontinuous production in process industries (e.g., chemical, pharmaceutical, or metal casting industries) where intermediate storage facilities and renewable resources (processing units and manpower) of limited capacity have to be observed. First, different storage configurations typical of process industries are discussed. Second, a basic scheduling problem covering the three above production modes is presented. Third, (exact and truncated) branch-and-bound methods for the basic scheduling problem and the special case of batch scheduling are proposed and subjected to an experimental performance analysis. The solution approach presented is flexible and in principle simple, and it can (approximately) solve relatively large problem instances with sufficient accuracy.

Batch scheduling in process industries: an application of resource-constrained project scheduling

The paper deals with batch scheduling problems in process industries where final products arise from several successive chemical or physical transformations of raw materials using multi–purpose equipment. In batch production mode, the total requirements of intermediate and final products are partitioned into batches. The production start of a batch at a given level requires the availability of all input products. We consider the problem of scheduling the production of given batches such that the makespan is minimized. Constraints like minimum and maximum time lags between successive production levels, sequence–dependent facility setup times, finite intermediate storages, production breaks, and time–varying manpower contribute to the complexity of this problem. We propose a new solution approach using models and methods of resource–constrained project scheduling, which (approximately) solves problems of industrial size within a reasonable amount of time.

Optimización de la programación(scheduling) en Talleres de Mecanizado

Los problemas de programación de tareas son muy importantes en el mundo actual. Se puede decir que se presentan en todos los fundamentos de la industria moderna, de ahí la importancia de que estos sean óptimos, de forma que se puedan ahorrar recursos que estén asociados al problema. La programación adecuada de trabajos en procesos de manufactura, constituye un importante problema que se plantea dentro de la producción en muchas empresas. El orden en que estos son procesados, no resulta indiferente, sino que determinará algún parámetro de interés, cuyos valores convendrá optimizar en la medida de lo posible. Así podrá verse afectado el coste total de ejecución de los trabajos, el tiempo necesario para concluirlos o el stock de productos en curso que será generado. Esto conduce de forma directa al problema de determinar cuál será el orden más adecuado para llevar a cabo los trabajos con vista a optimizar algunos de los anteriores parámetros u otros similares. Debido a las limitaciones de las técnicas de optimización convencionales, en la presente tesis se presenta una metaheurística basada en un Algoritmo Genético Simple (Simple Genetic Algorithm, SGA), para resolver problemas de programación de tipo flujo general (Job Shop Scheduling, JSS) y flujo regular (Flow Shop Scheduling, FSS), que están presentes en un taller con tecnología de mecanizado con el objetivo de optimizar varias medidas de desempeño en un plan de trabajo. La aportación principal de esta tesis, es un modelo matemático para medir el consumo de energía, como criterio para la optimización, de las máquinas que intervienen en la ejecución de un plan de trabajo. Se propone además, un método para mejorar el rendimiento en la búsqueda de las soluciones encontradas, por parte del Algoritmo Genético Simple, basado en el aprovechamiento del tiempo ocioso. ABSTRACT The scheduling problems are very important in today's world. It can be said to be present in all the basics of modern industry, hence the importance that these are optimal, so that they can save resources that are associated with the problem. The appropriate programming jobs in manufacturing processes is an important problem that arises in production in many companies. The order in which they are processed, it is immaterial, but shall determine a parameter of interest, whose values agree optimize the possible. This may be affected the total cost of execution of work, the time needed to complete them or the stock of work in progress that will be generated. This leads directly to the problem of determining what the most appropriate order to carry out the work in order to maximize some of the above parameters or other similar. Due to the limitations of conventional optimization techniques, in this work present a metaheuristic based on a Simple Genetic Algorithm (Simple Genetic Algorithm, SGA) to solve programming problems overall flow rate (Job Shop Scheduling, JSS) and regular flow (Flow Shop Scheduling, FSS), which are present in a workshop with machining technology in order to optimize various performance measures in a plan. The main contribution of this thesis is a mathematical model to measure the energy consumption as a criterion for the optimization of the machines involved in the implementation of a work plan. It also proposes a method to improve performance in finding the solutions, by the simple genetic algorithm, based on the use of idle time.

Integrated component scheduling models for chip shooter machines

This paper focuses on minimizing printed circuit board (PCB) assembly time for a chipshootermachine, which has a movable feeder carrier holding components, a movable X–Y table carrying a PCB, and a rotary turret with multiple assembly heads. The assembly time of the machine depends on two inter-related optimization problems: the component sequencing problem and the feeder arrangement problem. Nevertheless, they were often regarded as two individual problems and solved separately. This paper proposes two complete mathematical models for the integrated problem of the machine. The models are verified by two commercial packages. Finally, a hybrid genetic algorithm previously developed by the authors is presented to solve the model. The algorithm not only generates the optimal solutions quickly for small-sized problems, but also outperforms the genetic algorithms developed by other researchers in terms of total assembly time.

A heuristic approach for component scheduling on a high-speed PCB assembly machine

The collect-and-place machine is one of the most widely used placement machines for assembling electronic components on the printed circuit boards (PCBs). Nevertheless, the number of researches concerning the optimisation of the machine performance is very few. This motivates us to study the component scheduling problem for this type of machine with the objective of minimising the total assembly time. The component scheduling problem is an integration of the component sequencing problem, that is, the sequencing of component placements; and the feeder arrangement problem, that is, the assignment of component types to feeders. To solve the component scheduling problem efficiently, a hybrid genetic algorithm is developed in this paper. A numerical example is used to compare the performance of the algorithm with different component grouping approaches and different population sizes.

An approach to the development of expert systems within production planning and control

The thesis presents an account of an attempt to utilize expert systems within the domain of production planning and control. The use of expert systems was proposed due to the problematical nature of a particular function within British Steel Strip Products' Operations Department: the function of Order Allocation, allocating customer orders to a production week and site. Approaches to tackling problems within production planning and control are reviewed, as are the general capabilities of expert systems. The conclusions drawn are that the domain of production planning and control contains both `soft' and `hard' problems, and that while expert systems appear to be a useful technology for this domain, this usefulness has by no means yet been demonstrated. Also, it is argued that the main stream methodology for developing expert systems is unsuited for the domain. A problem-driven approach is developed and used to tackle the Order Allocation function. The resulting system, UAAMS, contained two expert components. One of these, the scheduling procedure was not fully implemented due to inadequate software. The second expert component, the product routing procedure, was untroubled by such difficulties, though it was unusable on its own; thus a second system was developed. This system, MICRO-X10, duplicated the function of X10, a complex database query routine used daily by Order Allocation. A prototype version of MICRO-X10 proved too slow to be useful but allowed implementation and maintenance issues to be analysed. In conclusion, the usefulness of the problem-driven approach to expert systems development within production planning and control is demonstrated but restrictions imposed by current expert system software are highlighted in that the abilities of such software to cope with `hard' scheduling constructs and also the slow processing speeds of such software can restrict the current usefulness of expert systems within production planning and control.

Multi-level genetic algorithm for the resource-constrained re-entrant scheduling problem in the flow shop

The re-entrant flow shop scheduling problem (RFSP) is regarded as a NP-hard problem and attracted the attention of both researchers and industry. Current approach attempts to minimize the makespan of RFSP without considering the interdependency between the resource constraints and the re-entrant probability. This paper proposed Multi-level genetic algorithm (GA) by including the co-related re-entrant possibility and production mode in multi-level chromosome encoding. Repair operator is incorporated in the Multi-level genetic algorithm so as to revise the infeasible solution by resolving the resource conflict. With the objective of minimizing the makespan, Multi-level genetic algorithm (GA) is proposed and ANOVA is used to fine tune the parameter setting of GA. The experiment shows that the proposed approach is more effective to find the near-optimal schedule than the simulated annealing algorithm for both small-size problem and large-size problem. © 2013 Published by Elsevier Ltd.

Decision support system for production control: Multiple criteria decision making in practice

This paper presents a development of decision support systems for solving scheduling problems. It consists of two parts — the first describing the production processes which can be handled by the system and the second describing how the system works.