Minimizing the cycle time of multiple-product processing networks with a fixed operation sequence,setups, and time-window constraints

We solve a special case of the single-robot cyclic scheduling problem with a fixed robot operation sequence and time window constraints on processing times. It generalizes the known single-part fixed-sequence problems into the one to cover a processing network with multiple part types and setup time requirements between the processing steps for different parts at the shared stations. The objective is to minimize the cycle time. We prove that this problem is equivalent to the parametric critical path problem, and propose a strongly polynomial time solution algorithm which uses a new labeling procedure to identify all feasible parameter values. The proposed algorithm is based on an extension to the known Bellman–Ford algorithm.     

Fast approximation algorithm for job sequencing with deadlines

The problem under consideration is to schedule jobs on a machine in order to minimize the sum of the penalties of delayed jobs. A “range-and-bound” method is proposed for finding a tight bound P? such that P?≤P1≤2P?, P1 being the minimal sum desired. The considered scheduling problem, for n jobs and accuracy ε > 0, is solved by a fully polynomial ε-approximation algorithm in $\text{O(n}{}^2\text{log n +}\text{n}{}^2\text{ε}\text{)}$ time and $\text{O(}\text{n}{}^2\text{ε}\text{)}$ space.     

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.     

Cyclic multiple-robot scheduling with time-window constraints using a critical path approach

An automated production system is considered in which several robots are used for transporting parts between workstations following a given route in a carousel mode. The problem is to maximize the throughput rate. Extending previous works treating scheduling problems for a single robot, we consider a more realistic case in which workstations are served by multiple robots. A graph model of the production process is developed, making it possible to apply PERT–CPM solution techniques. The problem is proved to be solvable in polynomial time.     

Spin-glass, antiferromagnetism and kondo behavior in Ce2Au1−x Co x Si3 alloys

Recently, the solid solution Ce₂Au_{1− x Co} xSi₃ has been shown to exhibit many magnetic anomalies associated with the competition between magnetic ordering and the Kondo effect. Here we report high pressure electrical resistivity of Ce₂AuSi₃, ac susceptibility (X) and magnetoresistance of various alloys of this solid solution in order to gain better knowledge of the magnetism of these alloys. High pressure resistivity behavior is consistent with the proposal that Ce₂AuSi₃ lies at the left-hand side of the maximum in Doniach’s magnetic phase diagram. The ac X data reveal that there are in fact two magnetic transitions, one at 2 K and the other at 3 K for this compound, both of which are spin-glass-like. However, as the Co concentration is increased, antiferromagnetism is stabilized for intermediate compositions before attaining non-magnetism for the Co end member.     

The growth of a single crystal of Sr3CuIrO6 and its magnetic behavior compared to polycrystals

We have grown single crystals of the psuedo-one-dimensional compound Sr₃CuIrO₆, a K₄CdCl₆-derived monoclinic structure with Cu-Ir chains along the [101] direction. We present the ac and dc magnetization behavior of the single crystals in comparison with that of the polycrystalline form reported earlier. There is a distinct evidence for at least two magnetic transitions, at 5 K (T ₁) and 19 K (T ₂), with different relative magnitudes in the single and polycrystals. The low temperature magnetic relaxation behavior of both the forms is found to be widely different, exhibiting unexpected time dependence.     

Flowshop Scheduling of Robotic Cells with Job-dependent Transportation and Set-up Effects

A flexible manufacturing cell consisting of two machining centres, several automated storage/retrieval stations, and a mobile transporting robot is considered. The problem is to schedule jobs on machines so as to minimize the makespan, with the effects of transportation and set-ups to be taken into account. The problem is studied with the aid of a graph model, and an exact algorithm of cubic complexity is derived based on the Gilmore–Gomory algorithm for the travelling salesman problem.     

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.     

An efficient algorithm for multi-hoist cyclic scheduling with fixed processing times

We consider no-wait production processes, where identical products are processed sequentially on n machines and transported by programmable hoists. We present an O(n⁵) algorithm that determines the minimum number of hoists required for all possible cycle-times; given the number of hoists, it also finds the minimum-time cyclic hoist-schedule.