The four papers in this special section are devoted to the topic of radio frequency identification (RFID), new areas of technological development, and applications for its use.

The present paper proposes a model for studying the system dynamics of an urban network under varying input flows and capacity constraints of the network. A simulation software has been developed using the dynamic network model that generates the travel times on the various paths of the network given the discrete input flows at the entrance, the initial system state and the characteristics of the network. The simulation software obtained is able to guide a car in the network to reach a given output in the minimum time whatever be the evolution of the state of the system with time.

In this paper, the expression "production systems" refers to flow shops, job shops, assembly systems, Kanban systems, and, in general, to any discrete event system which transforms raw material and/or components into products and/or components. Such a system is said to be cyclic if it provides the same sequence of products indefinitely. A schedule of a cyclic production system is defined as soon as the starting time of each operation on the related resource is known. It has been shown that, whatever the feasible schedule applied to the cyclic production system, it is always possible to fully utilize the bottleneck resource. In other words, it is always possible to maximize the throughput of such a system. As a consequence, we aim at finding the schedule which permits to maximize the throughput with a work in process as small as possible. We propose a heuristic approach based on Petri nets to find a near-optimal, if not optimal, solution. We also give a sufficient condition for a solution to be optimal.

This paper is divided in two parts. In the first part, we consider the case where several providers feed a single manufacturing unit periodically for certain specified demand. The cost incurred when a provider feeds the manufacturing unit is a concave function of the quantity delivered. Furthermore, each provider either delivers a quantity that lies between a minimum and maximum value or do not deliver any thing. We are introducing some properties of optimal solution and derive a heuristic algorithm from these properties. A numerical example illustrates this approach. In the second part of the paper, we consider the case where several providers feed periodically several manufacturing units. A heuristic algorithm is proposed. The results provided by this algorithm are compared with the optimal solution for the costs that are linear for a strictly positive quantity and equal to zero otherwise.

We consider the case of a single resource. A given schedule (possibly optimal) is evaluated by means of the sum of the delays of the tasks. A task appears in the system at a random time. The duration of this task is random, as well as its due date. The goal is to complete the task at the latest by its due date while increasing as little as possible the sum of the delays of the initial tasks. We have to find an algorithm that reduces as most as possible the amount of computation to be performed in real time at the expenses of the amount of computation to be performed off-line.

We consider single machine scheduling problems in which due dates are assigned according to the CON (common due date) rule. The objective in this problem is to find an optimal value of the due date and the related optimal schedule in order to optimize a given criterion based on the due date and the completion times of jobs.

This paper presents a low-complexity algorithm for online job scheduling at workcenters along a given route in a manufacturing system. At each workcenter, the job has to be processed by any one of a given set of identical machines. Each machine has a preset schedule of operations, leaving out time-windows during which the job's processing must be scheduled. The manufacturing system has no internal buffers and the job cannot wait between two consecutive operations. There is some flexibility in the job's processing times, which must be confined to given time intervals. The scheduling algorithm minimizes the job's completion time, and it is executable in real time whenever the job requirement is generated.

This paper proposes a model and a related algorithm for generating optimal cyclic schedules of hoist moves with time window constraints in a printed circuit board (PCB) electroplating facility. The algorithm is based on the branch and bound approach and requires the solution of a specific class of linear programming problems (LPP). These LPP are equivalent to the problems of the cycle time evaluation in bi-valued graphs. Computational experience is presented to compare the results obtained using this new algorithm with the ones proposed in the literature.

Concerns the use of Lagrangean relaxation for complex scheduling problems. The technique has been used to obtain near-optimal solutions for single machine and parallel machine problems. It consists of relaxing capacity constraints using Lagrange multipliers. The relaxed problem can be decomposed into independent job level subproblems. Luh et al. (1990, 1991) extended the technique to general job shop scheduling by introducing additional Lagrangean multipliers to relax precedence constraints, so that each job level relaxed subproblem can be further decomposed into a set of operation level subproblems which can easily be solved by enumeration. Unfortunately, the operation level subproblems exhibit solution oscillation from iteration to iteration and, in many cases, prevent convergence. Although several methods to prevent oscillation have been proposed, none is satisfactory. We propose an efficient pseudo-polynomial time dynamic programming algorithm. We show that, by extending the technique to job shop scheduling problems, the relaxation of the precedence constraints becomes unnecessary, and thus the oscillation problem vanishes. This algorithm significantly improves the efficiency of the Lagrangean relaxation approach to job-shop scheduling, and makes it possible to optimize "min-max" criteria by Lagrangean relaxation. These criteria have been neglected in the Lagrangean relaxation literature due to their indecomposability. Computational results are given to demonstrate the improvements due to this algorithm.

This paper introduces a class of Petri nets which are reversible, live, and can be kept bounded. Furthermore, these Petri nets have output transitions that can be fired independently from each other. These properties are required when modeling manufacturing systems. Another important property is that the integration of models which belong to this class of Petri nets still belongs to the same class, assuming that the integration is performed following rules which reflect common manufacturing practice. As a result, the qualitative properties of the module models are preserved. The results obtained in this paper are expected to shed light on the design, management and control of large scale manufacturing systems since modular approach is a way to cope with complexity.

We consider a single machine scheduling problem which we studied to improve the efficiency of an automated medical laboratory. In this problem, there are not only chain structured precedence constraints, but also minimal and maximal times separating successive jobs in the same chain (separation time windows). The criterion to be minimized is the makespan. Potential applications are not restricted to medical analysis. This problem often arises in systems where chemical processes are involved. Therefore the problem studied in this paper is important in practice. We prove that the problem is nonpolynomial (NP)-complete. As a consequence, we propose three heuristics for large size problems and a branch and bound based algorithm for small size problems. Computational results are reported.

Lagrangian relaxation consists of relaxing capacity constraints using Lagrangian multipliers and of decomposing the problem into job level subproblems. In the literature, when job shop scheduling problems are considered, these subproblems are further decomposed into operation level subproblems by relaxing precedence constraints. Unfortunately, this results in solution oscillation and often prevents convergence of the algorithm. Although several methods have been proposed to avoid solution oscillation, none of them is really satisfactory. In this paper, we propose an efficient pseudopolynomial time dynamic programming algorithm to solve relaxed job level subproblems. This makes the relaxation of precedence constraints unnecessary. The solution oscillation can then be avoided. This algorithm also results in a much more efficient Lagrangian relaxation approach to job-shop scheduling problems. Computational results on randomly generated problems are given to demonstrate the efficiency of the algorithm.

Use is made of event graphs, a particular type of Petri net, to evaluate job shops when manufacturing times are random variables and the control is defined as the sequence of product types at the entrance of each machine. Under very general assumptions, the cycle time of the system converges in probability to a constant. A heuristic algorithm which leads to a near-optimal solution of the problem (an optimal solution being the minimal work-in-process which allows the maximal productivity, i.e. the minimal cycle time, knowing the control) is derived from previous results.>

The purpose of this paper is to show how to decompose a scheduling problem into smaller subproblems as independant as possible, and to suggest an approach to take into account the remaining links between these subproblems.