Scheduling in robotic cells: Complexity and steady state analysis

This paper considers the scheduling of operations in a manufacturing cell that repetitively produces a family of similar parts on several machines served by a robot. The decisions to be made include finding the robot move cycle and the part sequence that jointly minimize the production cycle time, or equivalently maximize the throughput rate. We focus on complexity issues and steady state performance. In a three machine cell producing multiple part-types, we prove that in two out of the six potentially optimal robot move cycles for producing one unit, the recognition version of the part sequencing problem is unary NP-complete. The other four cycles have earlier been shown to define efficiently solvable part 'sequencing problems. The general part sequencing problem not restricted to any robot move cycle in a three machine cell is shown to be unary NP-complete. Finally, we discuss the ways in which a robotic cell converges to a steady state.     

Throughput optimization in robotic cells with input and output machine buffers: A comparative study of two key models

We consider the problem of scheduling operations in a robotic cell processing a single part type. Each machine in the cell has a one-unit input buffer and a one-unit output buffer. The machines and buffers are served by one single gripper robot. The domain considered is free-pickup cells with additive inter-machine travel time. The processing constraints specify the cell to be a flow shop. The objective is to find a cyclic sequence of robot moves that minimizes the long-run average time to produce a part or, equivalently, maximizes throughput. Bufferless robotic cells have been studied extensively in the literature. However, the few studies of robotic cells with output buffers at each machine have shown that the throughput can be improved by such a configuration. We show that there is no throughput advantage in providing machine input buffers in addition to output buffers. The equivalence in throughput between the two models has significant practical implications, since the cost of providing additional buffers at each machine is substantial.     

A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case

In this paper we consider the problem of no-wait cyclic scheduling of identical parts in an m-machine production line in which a robot is responsible for moving each part from a machine to another. The aim is to find the minimum cycle time for the so-called 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. The earlier known polynomial-time algorithms for this problem are applicable only under the additional assumption that the robot travel times satisfy the triangle inequalities. We lift this assumption on robot travel times and present a polynomial-time algorithm with the same time complexity as in the metric case, O(m⁵logm).     

An improved algorithm for cyclic flowshop scheduling in a robotic cell

This paper addresses a cyclic robot scheduling problem in an automated manufacturing line in which a single robot is used to move parts from one workstation to another. The objective is to minimize the cycle length. Previously known algorithms are either heuristic or at best polynomial of the fifth degree in the number of machines, m. We derive an exact scheduling algorithm solving the problem in O(m³ log m) time.     

Cyclic scheduling of a 2-machine robotic cell with tooling constraints

In this study, we deal with the robotic cell scheduling problem with two machines and identical parts. In an ideal FMS, CNC machines are capable of performing all the required operations as long as the required tools are stored in their tool magazines. However, this assumption may be unrealistic at times since the tool magazines have limited capacity and in many practical instances the required number of tools exceeds this capacity. In this respect, our study assumes that some operations can only be processed on the first machine while some others can only be processed on the second machine due to tooling constraints. Remaining operations can be processed on either machine. The problem is to find the allocation of the remaining operations to the machines and the optimal robot move cycle that jointly minimize the cycle time. We prove that the optimal solution is either a 1-unit or a 2-unit robot move cycle and we present the regions of optimality. Finally, a sensitivity analysis on the results is conducted.     

Cyclic scheduling in robotic flowshops

Fully automated production cells consisting of flexible machines and a material handling robot have become commonplace in contemporary manufacturing systems. Much research on scheduling problems arising in such cells, in particular in flowshop-like production cells, has been reported recently. Although there are many differences between the models, they all explicitly incorporate the interaction between the materials handling and the classical job processing decisions, since this interaction determines the efficiency of the cell. This paper surveys cyclic scheduling problems in robotic flowshops, models for such problems, and the complexity of solving these problems, thereby bringing together several streams of research that have by and large ignored one another, and describing and establishing links with other scheduling problems and combinatorial topics. This revised version was published online in June 2006 with corrections to the Cover Date.     

A faster algorithm for 2-cyclic robotic scheduling with a fixed robot route and interval processing times

Consider an m-machine production line for processing identical parts served by a mobile robot. The problem is to find the minimum cycle time for 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. This work treats a special case of the 2-cyclic robot scheduling problem when the robot route is given and the operation durations are to be chosen from prescribed intervals. The problem was previously proved to be polynomially solvable in O(m⁸log m) time. This paper proposes an improved algorithm with reduced complexity O(m⁴).     

Scheduling a two-machine robotic cell: A solvable case

The paper deals with the scheduling of a robotic cell in which jobs are processed on two tandem machines. The job transportation between the machines is done by a transportation robot. The robotic cell has limitations on the intermediate space between the machines for storing the work-in-process. What complicates the scheduling problem is that the loading/unloading operation times are non-negligible. Given the total number of operationsn, an optimalO(n logn)-time algorithm is proposed together with the proof of optimality.     

Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots

This paper addresses cyclic scheduling of a no-wait robotic cell with multiple robots. In contrast to many previous studies, we consider r-degree cyclic (r > 1) schedules, in which r identical parts with constant processing times enter and leave the cell in each cycle. We propose an algorithm to find the minimal number of robots for all feasible r-degree cycle times for a given r (r > 1). Consequently, the optimal r-degree cycle time for any given number of robots for this given r can be obtained with the algorithm. To develop the algorithm, we first show that if the entering times of r parts, relative to the start of a cycle, and the cycle time are fixed, minimizing the number of robots for the corresponding r-degree schedule can be transformed into an assignment problem. We then demonstrate that the cost matrix for the assignment problem changes only at some special values of the cycle time and the part entering times, and identify all special values for them. We solve our problem by enumerating all possible cost matrices for the assignment problem, which is subsequently accomplished by enumerating intervals for the cycle time and linear functions of the part entering times due to the identification of the special values. The algorithm developed is shown to be polynomial in the number of machines for a fixed r, but exponential if r is arbitrary.     

An optimization-based heuristic for the robotic cell problem

This study investigates an optimization-based heuristic for the robotic cell problem. This problem arises in automated cells and is a complex flow shop problem with a single transportation robot and a blocking constraint. We propose an approximate decomposition algorithm. The proposed approach breaks the problem into two scheduling problems that are solved sequentially: a flow shop problem with additional constraints (blocking and transportation times) and a single machine problem with precedence constraints, time lags, and setup times. For each of these problems, we propose an exact branch-and-bound algorithm. Also, we describe a genetic algorithm that includes, as a mutation operator, a local search procedure. We report the results of a computational study that provides evidence that the proposed optimization-based approach delivers high-quality solutions and consistently outperforms the genetic algorithm. However, the genetic algorithm delivers reasonably good solutions while requiring significantly shorter CPU times.     

A general model for cyclic machine scheduling problems

A general framework for modeling and solving cyclic scheduling problems is presented. The objective is to minimize the cycle time. The model covers different cyclic versions of the job-shop problem found in the literature, robotic cell problems, the single hoist scheduling problem and tool transportation between the machines.It is shown that all these problems can be formulated as mixed integer linear programs which have a common structure. Small instances are solved with CPLEX. For larger instances tabu search procedures have been developed. The main ideas of these methods are indicated.     

Simultaneously scheduling multiple turns for steel color-coating production

This paper investigates a large-scale scheduling problem in the iron and steel industry, called color-coating production scheduling (CCPS). The problem is to generate multiple production turns for the galvanized coils that dynamically arrive from upstream lines within a given scheduling horizon, and at the same time determine the sequence of these turns so that the productivity and product quality are maximized while the production cost and the number of generated turns are minimized. We formulate this problem as a mixed integer nonlinear program and propose a tabu search heuristic to obtain satisfactory solutions. Results on real production instances show that the presented model and heuristic are more effective and efficient with comparison to manual scheduling. A practical scheduling system for CCPS combining the model and heuristic has been developed and successfully implemented in a major iron and steel enterprise in China.     

A weighted independent even factor algorithm

An even factor in a digraph is a vertex-disjoint collection of directed cycles of even length and directed paths. An even factor is called independent if it satisfies a certain matroid constraint. The problem of finding an independent even factor of maximum size is a common generalization of the nonbipartite matching and matroid intersection problems. In this paper, we present a primal-dual algorithm for the weighted independent even factor problem in odd-cycle-symmetric weighted digraphs. Cunningham and Geelen have shown that this problem is solvable via valuated matroid intersection. Their method yields a combinatorial algorithm running in O(n ³ γ +? n ⁶ m) time, where n and m are the number of vertices and edges, respectively, and γ is the time for an independence test. In contrast, combining the weighted even factor and independent even factor algorithms, our algorithm works more directly and runs in O(n ⁴ γ?+?n ⁵) time. The algorithm is fully combinatorial, and thus provides a new dual integrality theorem which commonly extends the total dual integrality theorems for matching and matroid intersection.     

A review of TSP based approaches for flowshop scheduling

Contemporary flowshops that are variants of the classical flowshop frequently pose challenging scheduling problems. Such flowshops include no-wait, blocking, and robotic flowshops. These may sometimes be modeled as traveling salesman problems (TSP) and then solved using efficient algorithms available for the TSP. Encountered in auto, electronic, chemical, steel and even modern service industries, such problems are reviewed in this paper. We show that the TSP based approach is quite effective over a broad range. It tackles no-wait flowshops, blocking flowshops, group scheduling of parts in a flowshop using a generalized extension of the TSP, lot streaming and scheduling problems, and as recently done, scheduling of parts and robot movements in automated production cells. In this review paper, we describe several well-documented applications of no-wait and blocking scheduling models and illustrate some ways in which the increasingly used modern manufacturing systems such as robotic cells may be modeled as TSP. We also review the computational complexity of a wide variety of flowshop models. Finally, we suggest some fruitful directions for future research.     

A bijective proof of Jackson's formula for the number of factorizations of a cycle

Factorizations of the cyclic permutation into two permutations with respectively n and m cycles, or, equivalently, unicellular bicolored maps with N edges and n white and m black vertices, have been enumerated independantly by Jackson and Adrianov using evaluations of characters of the symmetric group. In this paper we present a bijection between unicellular partitioned bicolored maps and couples made of an ordered bicolored tree and a partial permutation, that allows for a combinatorial derivation of these results.Our work is closely related to a recent construction of Goulden and Nica for the celebrated Harer-Zagier formula, and indeed we provide a unified presentation of both bijections in terms of Eulerian tours in graphs.     

An algorithm to generate the ideals of a partial order

Generating the ideals of a partially ordered set is an important, frequently occurring problem in scheduling, reliability, sensitivity analysis for network flows and other combinatorial optimization problems. In this paper we present an algorithm which generates all the ideals of a partial order on n elements in O(n) time per ideal.     

Cyclic scheduling for F.M.S.: Modelling and evolutionary solving approach

This paper concerns the domain of flexible manufacturing systems (FMS) and focuses on the scheduling problems encountered in these systems. We have chosen the cyclic behaviour to study this problem, to reduce its complexity. This cyclic scheduling problem, whose complexity is NP-hard in the general case, aims to minimise the work in process (WIP) to satisfy economic constraints. We first recall and discuss the best known cyclic scheduling heuristics. Then, we present a two-step resolution approach. In the first step, a performance analysis is carried out; it is based on the Petri net modelling of the production process. This analysis resolves some indeterminism due to the system’s flexibility and allows a lower bound of the WIP to be obtained. In the second step, after a formal model of the scheduling problem has been given, we describe a genetic algorithm approach to find a schedule which can reach the optimal production speed while minimizing the WIP. Finally, our genetic approach is validated and compared with known heuristics on a set of test problems.     

Cyclic scheduling of offweekends

This paper addresses the following problem. Given a set of m positive integers and two other positive integers A and B with A < B and A ⪯ m, does there exist a cyclic ordering of the m integers such that the sum of any A consecutive integers in the ordering is at most B? The problem has application in the scheduling of offweekends in manpower scheduling problems. A hypergraph model of the problem is presented which gives necessary and sufficient conditions on A, B and the set of m integers when A = 1 and A = 2. When A > 3 such conditions are unknown. However, conditions are given for the special case where any two of the m integers differ by at most one which models the common requirement, in manpower scheduling, of an even distribution of offweekends.