Skip to main content

About this book

Striking a balance between state-of-the-art research and practical applications, this book provides a forum for contributions that cover the main research challenges in the cyclic modeling, development, and validation of concurrently acting distributed production systems: systems that employ multi-assortment production in large quantities, are characterized by gradual changes in their product mix, and exclusively manufacture products in a cyclic manner. Similar issues also arise in computer systems, e.g., embedded systems. Cyclic optimization problems that occur in them are unique and under-researched, but are attracting new interest primarily due to their great practical importance and the difficulty involved in obtaining efficient algorithms for solving specific cases with real constraints arising from manufacturing practice. Addressing these and other topics, the book will be of great interest to researchers in computer science, operations management, and production control, as well as practicing managers and engineers.

Table of Contents


Graph Modeling of Cyclic Systems


Cyclic Data Flows in Computers and Embedded Systems

Synchronous DataFlow Graphs (SDF in short) is a simple model of computation introduced for the description of Digital Signal Processing Applications. This formalism is today widely used to model embedded parallel applications. This chapter aims at presenting a panorama of theoretical results and practical applications in connection with cyclic scheduling problems. We first recall that the execution of a SDF can be seen as a set of cyclic dependant tasks. The structure of precedence constraints, important dominance properties and simplifications of the SDF are then presented. For the special case of uniform precedence graph, periodic schedule are dominant and the maximum throughput can be polynomially evaluated. Main results on the resource constrained problem are presented, followed by a more recent problem issued from sensor networks. In the general case, the existence of a polynomial-time algorithm to evaluate the maximum throughput of a SDF is a challenging question. However, the determination of a periodic schedule of minimum period is a polynomial problem, and many authors limit their study to this class of schedule to express optimization problems as the total buffer minimization or to evaluate the latency of a real-time periodic system.
Claire Hanen, Alix Munier-Kordon

Cyclic Two Machine Flow Shop with Disjoint Sequence-Dependent Setups

The chapter considers the problem of cyclical jobs scheduling on two machines with resource constraints often encountered in practice, and concerning a number of teams that can perform setups of machines between jobs performed. We are considering a fundamental and most restrictive case with only one setup team. This limitation significantly impedes the considered issue because the solution is represented here not only by the order of performing jobs, but also by the route of the setup team, i.e. the order in which the team makes setups of machines.
Wojciech Bożejko, Czesław Smutnicki, Mariusz Uchroński, Mieczysław Wodecki

Cyclic Scheduling in the Manufacturing Cell

The chapter is devoted to scheduling of jobs performed by machines and by an operator in the automated manufacturing cell, which produces parts in large production batches. The purpose of scheduling is to determine a cyclical schedule that minimizes production cycle time. The chapter presents the original model of the problem that enables effective determination of cycle time for any sequence of operations in the cell. What is more, there was an algorithm proposed that determines the sequence and schedule of works minimizing the production cycle time.
Wojciech Bożejko, Jarosław Pempera, Czesław Smutnicki, Mieczysław Wodecki

On Estimating LON-Based Measures in Cyclic Assignment Problem in Non-permutational Flow Shop Scheduling Problem

In recent years, Fitness Landscape Analysis (FLA) has provided a variety of new methods to analyze problem instances, allowing for a better understanding of the challenges that operations research is facing. Many from the most promising FLA methods are based on Local Optima Networks (LON), a compact representation of a search space from the perspective of a optimization algorithms. In order to obtain a represantative LON, a solution space sampling procedure must be utilized. However, there is little known about the proper sampling methods—as well as the minimal ammout of computational effort required to sufficiently sample the space. In this chapter, we investigate the impact of the number of samples taken, on the obtained LON metrics for Cyclic Assignment Problem in non-permutational Flow Shop Scheduling Problem. The sampling process is performed in incremental steps, until the entire solution space is analyzed. After each step, LON measures are calculated. The results suggest a strong relation between the measure values and sampling effort.
Andrzej Gnatowski, Teodor Niżyński

Cyclic Route Planning


Coordination of Cyclic Motion Processes in Free-Ranging Multiple Mobile Robot Systems

We consider a Multiple Mobile Robot System (MMRS) viewed as a group of autonomous robots sharing a common 2D motion space. Each robot performs a mission that requires it to travel a number of times along a specific, independently planned closed path. The robots operate asynchronously and are able to control their motion with path-following algorithms that allow each of them to correctly perform its mission when alone on the stage. When sharing the motion space, the robots must refine their motion strategies in order to avoid collisions, through modification of their paths, velocity profiles or both. Following our earlier contributions, we represent MMRS as a class of RAS (Resource Allocation System) that abstracts in a discrete form the motion space and the motion processes of the robots. A model of the feasible dynamic behavior of the robot system is then obtained by mapping the distinguished RAS into a DFSA (Deterministic Finite State Automaton) that ensures collision avoidance among the robots. Based on this model, we formulate the deadlock avoidance problem, discuss its complexity, and demonstrate relevant algorithms to solve it. Finally, we propose a control architecture that implements the described control logic and combines it with the priority control, thus receiving a flexible controller for MMRS.
Elzbieta Roszkowska

Blockage-Free Route Planning for In-Plant Milk-Run Material Delivery Systems

In this chapter, two kinds of intertwined decisions regarding the movement of vehicles in an in-plant milk-run delivery system are considered: routing decisions, which determine the set of sequences of stations visited by each tugger train, and scheduling decisions, which plan congestion free movement of the tugger trains. The problem under study, called the Multi Trip and Multi Cycle Pick-up and Delivery Problem with Time Windows and Congestion Free Traffic, can be viewed as an extension of the pick-up and delivery problem with time windows in which multiple tugger trains travel along closed-loop congestion-free routes in different cycles. A declarative model of the investigated milk-run delivery principle makes it possible to formulate a vehicle routing and scheduling problem the solution to which determines the route, the time schedule, and the type and number of parts that the different trucks must carry to fulfill orders from various customers/recipients. Due to the requirement of congestion-free milk-run traffic, a scheduling period slicing principle allowing to synchronize cyclic flows of different periods is applied. Its implementation, resulting in a cyclic schedule composed of quasi cyclic sub-schedules, implies a recursive formulation of a well-known constraint satisfaction problem. The goal is to find solutions that can minimize both vehicle downtime and the takt time of the production flow. Computer experiments illustrate the possibility of using the present approach in real-life systems.
Grzegorz Bocewicz, Izabela Nielsen, Zbigniew Banaszak

Max-Plus Algebra for Cyclic Systems Modeling


Conflict Avoidance Within Max-Plus Fault-Tolerant Control: Application to a Seat Assembly System

Flexibility and agility are central requirements for future manufacturing systems (especially assembly systems), because in most industries the product variety and the fluctuations in demand are still increasing. An increase of the degree of flexibility allows more efficient activities aiming at following the dynamically evolving markets. Such systems should be able to react to changes of product, demands, increased varieties of products requirements concerning reduced delivery times and increased product quality. Therefore, a strong focus on the flexibility of manufacturing and assembly systems leads to economic advantages for industrial companies in terms of the system investment cost. In particular, the cost related to the reconfiguration of the system.
Marcin Witczak, Paweł Majdzik, Bogdan Lipiec, Ralf Stetter

Max-Plus Algebraic Modelling of Cyclical Multi-assortment Manufacturing System

In this chapter, multi-assortment production systems are considered, which can be described as Discrete Event Systems (DES). Due to the implementation of a certain number of products, they are characterized by repetitive, cyclical (rhythmic) behavior. Analyzing multi-assortment, cyclic production, there are a number of phenomena that have a direct impact on the behavior of systems, such as ending the production of one product or launching, in an already existing production system, the production of an additional, new product. And it is the modeling of such phenomena that is presented in this chapter.
Jarosław Stańczyk

Petri Nets for Cyclic Systems Modeling


Incorporating Automatic Model Checking into GPenSIM

Large-scale manufacturing systems involve hardware and software that are highly interconnected and complex. Unexpected failures in these systems can cause material damages and can risk human lives too. The definite way of avoiding unexpected failures is to make a model of the system and to perform model verification and validation on it. Petri nets are a highly effective way of modelling discrete-event systems. Model checking is the terminology that is used for model verification on Petri Nets. General-purpose Petri Net Simulator (GPenSIM) is a tool for modelling, simulation, performance evaluation, and control of discrete-event systems (GPenSIM: a general purpose Petri net simulator, http://​www.​davidrajuh.​net/​gpensim, 2019, [15]). GPenSIM is developed by one of the authors of this chapter. This chapter explores the potentials of incorporating the model checking functions to GPenSIM. In this chapter, the problem of model checking is presented. The chapter introduces Activity-Oriented Petri Nets (AOPN) and GPenSIM for model checking of cyclic production systems.
Reggie Davidrajuh, Bozena Skolud, Damian Krenczyk


Additional information

Premium Partner

    Image Credits