Search

Dans ce rapport de recherche, nous nous intéressons à la décomposition de réseaux urbains de grande taille en sous réseaux de taille limitée. Nous cherchons à minimiser les connexions entre sous réseaux. En d'autres termes, nous cherchons à minimiser le nombre de noeuds situés à la frontière entre sous réseaux. Ce travail s'intègre dans une démarche qui a pour but de fournir aux conducteurs de véhicules automobiles un support qui leur permet de trouver le chemin le plus rapide entre deux localisations données. Deux algorithmes notés RP-1 et RP-2 sont présentés dans ce qui suit. Dans chacun de ces algorithmes, chaque noeud constitue initialement un sous réseau. Dans le premier algorithme, deux sous réseaux sont agrégés à chaque pas. Les deux sous réseaux choisis sont ceux qui conduisent au sous réseau de densité minimale. La densité d'un sous réseau est le quotient du nombre de noeuds situés sur la frontière par le nombre de noeuds du sous réseau. Dans le second algorithme, nous choisissons le sous réseau de densité maximale et nous lui agrégeons le sous réseau densité maximale qui lui est connecté. Nous poursuivons le processus jusqu'à atteindre la taille maximale acceptée, puis nous recommençons le processus jusqu'à épuisement des noeuds. Dans le second algorithme, l'intensité est définie comme le rapport entre le nombre de connexions entre les sous réseaux et le nombre de noeuds dans le sous réseau agrégé. Ces deux algorithmes sont ensuite comparés, puis appliqués à un vaste réseau de la Ville de Paris.

Prediction of accurate travel time plays an important role in dynamic route guidance on urban networks. The dynamic traffic flows entering the network affect the behavior of the system and the free flow movement of vehicles. To study the complex system dynamics of an urban network under varying input flows, we begin with the basic unit of the network called a lane. The analysis of the behavior of a single lane is done to derive the travel time from the characteristics of the lane, the input flow and the constraints on the output flow. The system analysis of the single lane is then applied to the whole network for studying the transfer of flows inside the network. A dynamic network model has been proposed for the network analysis. A simulation software has been developed using the dynamic network model which generates travel times on the network using the input data as the flows coming at the entrances of the system, the initial system states of the lanes and the characteristics of the network.

The profit margin of retailers and suppliers are decreasing as more and more market players are joining the market. The customer generally switch to another brand / retailer as the price increases. Since supplier revenue depends upon the retailer's revenue; retailer's revenue indirectly depends upon the supplier's price and the customer demand; and customer demand depends upon the retail price hence it is necessary to have a business coordination to win the market. In this business partnership both partners coordinate with each other to decide the retail and wholesale price, profit margin and inventory level in stock in order to get big market share and hence higher revenue. In this paper we present a producer-retailer partnership model based on profit sharing. We assume that customer demand depends upon the retail price and tends to zero as the price of commodity tends to infinite. We propose an approach to maximize the combined profit and sharing the profit among partners proportional to their risk. The properties of the problem are explored and an optimal algorithm based on the results is presented.

This paper addresses the 0-1 outcome feature selection problem. In such a problem, a set of features leads to an outcome that is 0 or 1, depending upon the values of the features. The goal is to extract subsets of features that characterize at best outcome 1. This kind of problem arises in medical analysis, quality control and, generally, in any domain that requires series of expensive tests to evaluate the state of a system.

Dans ce papier nous étudions un système d'assemblage dans lequel les délais de réapprovisionnement des composants sont aléatoires. Nous supposons que la demande de produit final est déterministe et que le délai de livraison est connu. L'objectif est de trouver les instants de commande de chaque composant de façon à minimiser le coût moyen qui se compose d'un coût de stockage et d'un coût de retard. L'analyse du problème est compliquée par le fait que la densité de probabilité du délai de livraison peut être différente d'une composante à l'autre. Pour contourner la difficulté, nous divisons le problème en deux parties et résolvons ces parties en utilisant les résultas proposés dans le paragraphe 3. Finalement, l'algorithme est illustré par des exemples numériques.

This paper presents an approach to schedule a project online in a supply chain without rescheduling or disturbing the previous schedules. The information at hand are the project requirements and the resources availability i.e. the busy status of resources. The objective is to find the shortest project completion time while following the no-wait strategy. Three algorithms are proposed. The first algorithm schedules the jobs online optimally for production processes that do not include assembly operations. The second algorithm utilizes the functionality of the first algorithm for scheduling the ordinary assembly processes (single assembly operation at the end of the processes). The third algorithm extends the approach of ordinary assembly process to schedule the complex assembly processes. A complex assembly process contains one assembly operation (if it is not the last one) or more than one assembly operations.

We consider a system made of one resource. The execution of the tasks is non-preemptive on this resource. The tasks we consider are composed of a given number of subtasks, two consecutives subtasks being separated by an idle period. These idle periods may be used for executing other subtasks. We wish to insert a new task in a given schedule. The characteristics of this task are not known before it appears, and its execution must be completed before a given deadline. The criterion is the minimization of the increase of the sum of the delays of the tasks.

This paper addresses the problem of supply chain design at the strategic level when production/distribution of a new market opportunity has to be launched among a set of qualified partners. The new market opportunity is characterized by a deterministic forecast over a planning horizon. The product (or service) is assumed to be produced (or provided) in a fixed sequence of some distinct stages or echelons, and each stage could have a number of qualified partners. The qualified partners at each stage might be different factories (or service organization) of the same corporation or different organizations that have agreed to participate in an open supply web. We assume that the partners under consideration are equally capable at their respective processing stage (possibly through a pre-processing evaluation for the new opportunity), but the partners may differ in available capacities and costs, given their current workloads. The objective is to design the supply chain by selecting one partner from each stage to meet the forecasted demand without backlog and optimize fixed alliance related and variable production and logistics costs over the given planning horizon. A solution algorithm is developed based on key properties of the problem, and is tested on empirical data sets. The overall contribution is an analytical tool that can be employed by the coordinator of the new market opportunity at the strategic level for designing supply chains based on integrated cost concerns.

Prediction of accurate travel time is an important aspect in real time monitoring of the traffic behavior on a city network. The dynamic traffic flows entering the network affect the behavior of the system and the free flow movement of vehicles. To study the complex system dynamics arising due to varying input flows, we begin with a single lane system. The analysis of the behavior of the system is done to derive the travel time from the characteristics of the lane, the input flow and the constraints on the output flow.

This paper addresses the problem of supply chain design at the strategic level when production/distribution of a new market opportunity has to be launched in an existing supply chain. The new market opportunity is characterized by a deterministic forecast expected to occur per period. The product (or service) is assumed to be produced (or provided) in a three-stage capacitated supply chain where the first stage concerns suppliers, the second stage producers and the final stage customers. There could be multiple alternatives at each stage which are defined as nodes. Nodes in each stage are connected to the next stage through capacitated transportation systems. Production capacity at the second stage (i.e., producers) are also limited since they may already be involved in other existing activities. The objective is to perform strategic capacity planning in the supply chain in order to meet the demand of the new opportunity at minimal cost. A linear running cost is associated to each node. If the decision is to increase the capacity of a node, then a fixed cost applies followed by a cost that is proportional to the additional capacity The overall problem can be modelled as a large-scale mixed integer linear programming problem. A solution algorithm is developed to overcome difficultie- s associated with the size of the problem, and is tested on empirical data sets. The overall contribution is an analytical tool that can be employed by the managers responding to the new market opportunity at the strategic level for supply chain design.

In this paper, we introduce the notion of strategic model of supply chain. At the strategic level, a supply chain is always composed of five basic activities, denoted by Buy, Make, Move, Store and Sell. We present a specific model and show how to optimize the related supply chain from a strategic point of view

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 taskappears 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.

In the kind of transportation system studied in this paper, cars are placed at the disposal of subscribers (customers) in stations. Customers have access to the cars using non-contact smart cards. They can use a car for a while and return it in the same or another station. At some times of the day, either an overflow or a shortage of cars may happen at one or more stations. The balancing process consists of redistributing the cars among the stations in order to avoid overflow and shortage, that is to guaranty a service ratio that is as high as possible, taking into account the number of cars available in the system. The goal of this paper is to make a systematic analysis of the balancing process and to propose an efficient balancing heuristic algorithm.

In this paper, we address the problem of production systems having two characteristics. First, the manufacturing times can be chosen between given bounds. Such a production system is said to have controllable processing times. Second, an operation must start as soon as the previous operation on the same part (if any) is completed. A production system having this characteristic is said to be no-wait. Several on-line schedules are considered to minimize the makespan in flow shop and job shop situations. We prove that in the worst case, the makespan provided by these schedules is m times longer than the optimal one (for different flow shops and job shops), m being the number of machines. We give several related results on competitive ratio.

Nowadays, big cities have to face transportation problems which are crucial for their survival. One of the solutions that is currently spreading in developed countries is to put a pool of electric cars at the disposal of customers to make local journeys. In this kind of system, cars are parked in stations where their batteries are recharged. A customer uses an electric car to travel from on station to another. Then, if necessary, the same customer will later use another electric car to travel to a third station, and so on. It is easy to understand that the gravity center of the set of cars changes during the day. This requires an action that consists in transporting cars from stations having excess of cars to stations that many run out of cars soon. Such an action is called a balancing action. The goal of this paper is to propose a balancing method that consists in using a truck of a given capacity. This truck visits the stations following a given circuit, and either leaves cars in stations when needed or takes cars from stations where they are in excess. Indeed, this method analyses the state of the whole system in order to make a decision at the arrival of the truck in a station.

This paper is devoted to a class of problems which are modeled by a digraph, and such that each arc is characterized by several weights which depend on a parameter. This parameter takes its values in a set which characterizes the arc. The goal is to find a so-called parameterized path (i.e; a path and the values of the parameters corresponding to its arcs) that optimizes a criterion which is a combination of the weights of the arcs. The problem is introduced using transportation, communication and manufacturing problems. An unified formulation is provided, as well as an algorithm. A numerical example is proposed to illustrate this algorithm.

Management of projects often requires decisions concerning the choice of alternative activities. The completion time of the whole project (i.e. the makerpan) is computed subsequently. In this paper, we aim at selecting the activities and computing the makespan simultaneously. This problem is referred to as PERT Problem with Alternatives (PPA). The corresponding model is similar to a conventional PERT graph, except that two types of nodes are introduced to represent either the choice between activities, or the fact that a set of activities should be completed before starting a subsequent set of activities. In this paper, we analyse the PPA and we propose a pseudo-polynomial algorithm to solve it.

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 (DES) which transforms raw material and/or components into products and/or components. Such a system is said to be cyclic if it provides indefinitely the same sequence of products. 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 showed 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 productivity of such a system. As a consequence, we aim at finding the schedule which permits to maximize the productivity with a Work-In-Process (WIP) 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 addresses two real-life assignment problems. In both cases, the number of employees to whom tasks should be assigned is significantly greater than the number of tasks. In the simple job assignment problem, at most one task (job) should be assigned to each employee; this constraint is relaxed in the multiple job assignment problem. In both cases, the goal is to minimize the time the last task is completed; these problems are known as Bottleneck Assignment Problems (BAPs for short). We show that the simple job assignment problem can be solved optimally using an iterative approach based on dichotomy. At each iteration, a linear programming problem is solved: in this case the solution is integer. We propose a fast heuristic to solve the multiple job assignment problem, as well as a Branch-and-Bound approach which leads to an optimal solution. Numerical examples are presented. They show that the heuristic is satisfactory for the application at hand.

Management of projects often requires decisions concerning the choice of alternative activities. Then, the completion time of the whole project (i.e. the makerpan) is computed. In this paper, we aim at selecting the required activities simultaneously with the computation of the makespan. This problem is referred to as PERT Problem with Alternatives (PPA). The corresponding model is similar to a conventional PERT graph, except that two types of nodes are involved to represent either the choice between activities, or the fact that a set of activities should be completed before starting another set of activities. A formalization of the problem and some important properties concerning the optimal solution are given. Several well- solvable cases of the problem and a powerful decomposition algorithm running in polynomial time are presented. This decomposition is applicable for solving many real-life problems.

In this paper, we aim at providing a unified framework of the common due date assignment and scheduling problems in the deterministic case by surveying the literature concerning the models involving single machine and parallel machines. We focus on static production settings in which a fixed set of is available for processing as opposed to dynamic production settings where jobs continuously arrive in the system and should be scheduled on-line. The problems with due date determination have received considerable attention in the last ten years due to the introduction of new methods of inventory management such as Just-In-Time (JIT) systems. The common due date model which is also known in scheduling literature as CON model, where CON stands for constant flow allowance, corresponds, for instance, to an assembly system in which the components of the product should be ready at the same time, or to a shop where several jobs constitute a single customer's order. In the problems under consideration, the objective is to find an optimal value of the common 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. The results on the algorithms and complexity of the common due date assignment and scheduling problems are summarized.

This paper addresses the transportation problem using public electric cars. At each car station, a decision, concerning the cars which should become available to customers, has to be taken. We assume that a vehicle is available when its charge is greater than a given threshold. Our goal is to optimize this threshold.

This paper is concerned with inventory control in assembly systems for minimizing production costs. The system manufactures multiple products assembled from various components, and it operates according to a cyclic schedule. At the start of each cycle time, two decisions are made: the product volumes to be assembled during the current cycle, and the component-stock levels to be ordered. For a given decision, there is an associated cost incurred by backlogging of the finished products on one hand, and the component inventory holding cost, on the other hand. The objective here is to balance the two costs so as to minimize their sum. One complicating factor stems from uncertainties in both product demand levels and components yield times. These uncertainties can be modeled by probabilistic means, and hence the cost minimization problem becomes a stochastic problem. This problem can be quite difficult due to the nonlinearity of the equations involved, the mix of integer and continuous parameters, and their large number in moderate-size problems. Our approach in this paper is to first define certain control parameters and thus reduce the number of the variables involved in the optimization problem, and then solve the latter problem by using sophisticated optimization techniques in conjunction with heuristic modeling. We will demonstrate, by numerical means, the resolution of fairly difficult problems and thus establish the viability of the proposed numerical techniques

A real-time scheduling algorithm which guarantees an optimal makespan to each part which arrives in a line of chemical baths for surface treatment purpose is proposed. We first consider the case when the treatment preriods are much greater than the transportation times, which allows us to neglect these times. We then extend our approach to the case when transportation times cannot be neglected. Some numerical examples are provided to illustrate this approach.

In this paper, we consider the problem of scheduling tasks on unrelated parallel machines. Precedence constraints exist between the tasks, but their number is limited compared with the number of tasks. We propose a number of heuristics in order to find near-optimal solutions to the problem. Empirical results show that the heuristics are able to find very good approximate solutions.

The problem of scheduling n jobs on a single machine in order to minimize the weighted sum of earliness and tardiness in NP-complete when jobs have different due dates. In most of the papers dedicated to this problem, authors assume that there is no idle time between two consecutive jobs. However, as indicated by several authors, this assumption is not consistent with the earliness-tardiness criterion. It is the reason why we do not make this assumption in this paper. To reach an optimal solution, we propose a branch-and-bound approach which takes advantage of some dominance properties and lower bounding procedures. Numerical experiments show that the algorithm can solve this problem with up to twenty jobs in a reasonable amont of time.

Lagrangian relaxation has recently emerged as an important method for solving complex scheduling problems. The technique has succeesfully been used to obtain near-optimal solutions for one machine scheduling problems and parallel machine scheduling problems. The approach consists of relaxing the capacity constraints on machines by using Lagrangian multipliers. The relaxed problem can be decomposed into independent job level subproblems. Peter B. Luh and his colleagues extended the technique to general job shop scheduling problems by introducing more Lagrangian multipliers to relax the precedence constraints among operations. Such 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 of the algorithm. Although they have proposed several method to prevent solution from oscillation, none of the methods is really satisfactory. In this paper, we propose an efficient pseudopolynomial time dynamic programming algorithm to relaxed job level subproblems. We show that by extending the technique to job shop scheduling problems, the relaxation of the precedence constraints is un-necessary, and thus the oscillation problem vanishes. This algorithm also results in a much more efficient Lagrangian relaxation approach to job-shop scheduling problems. Furthermore, this algorithm makes it possible to optimize "min-max" criteria by Lagrangian relaxation. These criteria have been neglected in Lagrangian relaxation litterature for sake of indecomposability. Computational results on randomly generated problems are given to demonstrate the efficiency of the algorithm.

This paper considers scheduling problems in a robotic cell which produces a set of parts on several machines served by a robot. We study the problem of sequencing parts in the cell in order to minimize the production cycle time when the sequence of the robot moves is given. This problem is NP-hard for most of the one-unit robot move cycles in a robotic cell with more than two machines producing more than two part-types. We first give a mathematical formulation to the problem, and then propose a branch-and-bound algorithm to solve it. The bounding scheme of this algorithm is based on relaxing, for all the machines except two, the constraint that the machine is occupied by a part for a period at least as long as the processing time of the part. It turns out that the lower bound obtained in this way is tight. This relaxation allows us to overcome the complexity of the problem. The lower bound can be computed using the algorithm of Gilmory and Gilmore. Computational experiments on part sequencing problems in three-machine robotic cells are given.

Nous nous intéressons à l'optimisation de la planification d'un système d'assemblage multi-produits. Les composants sont commandés chez des fournisseurs extérieurs avec des délais de livraison non négligeables. Un même type de composant peut être utilisé pour l'assemblage de plusieurs types de produits. L'assemblage d'un produit demande un ou plusieurs composants de différents types. Nous étudions le fonctionnement du système en régime permanent. Nous supposons que la demande de chaque produit est identique à chaque période de temps, mais que les dates de livraisons des composants subissent des déviations aléatoires suivant des lois de distribution de probabilités quelconques mais connues. La capacité de production est supposée illimitée et les seuls coûts qui interviennent dans le critère à optimiser sont des coûts de stockage de composants et des coûts de rupture de produits finis. Pour résoudre ce problème, nous utilisons une technique d'horizon glissant en croisant un modèle de programmation linéaire, des calculs de prévisions et des méthodes de simulation. Nous présentons les caractéristiques fondamentales des modèles utilisés, des expérimentations numériques et une méthodologie d'utilisation pratique.

In the first part of this study, we provided a hierarchical model for mediumn- and short-term planning, as well as solution algorithms which iteratively provide near optimal solutions. In part 2, we evaluate these algorithms from different points of view. We first compare the hierarchical approach and the monolithic approach in terms of memory requirement and computational complexity. We then study the quality of production plans obtained using these algorithms. Finally, we present an industrial application and compose the results obtained using the hierarchical approach with those obtained by the MRP II system currently in use in the company.

Dans ce papier, nous nous intéressons à une propriété qualitative des réseaux de Petri : la bornitude structurelle. Nous mettons en évidence des conditions suffisantes dans différents cas de conception pour assurer la bornitude structurelle. Ces conditions nous permettent de vérifier la bornitude structurelle en n'examinant qu'une partie du système. En utilisant ces résultats, nous développons une méthode d'aide à la conception limitée à la vérification de la bornitude structurelle. Notons que cette propriété est indispensable dans les systèmes automatisés.

We consider a system the state of which is represented by the value of a unique variable. The state of the system can be observed at regular intervals of time. It evolves from one instant to the next one according to an exponential distribution. The system breakdowns if the state exceeds a given limit. In this case, it must be repaired, which results to a repair cost. It is also possible to maintain the system, i.e. to inspect it and, if required, adjust it before it breaks down. This results in a maintenance cost usually much smaller than the repair cost. We aim at defining a warning-value less than the breakdown limit such that, if the state lays between the warning value and the breakdown limit, a maintenance operation is performed to the system. The goal is to minimize the average cost.

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 (LPPs). These LPPs 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.

We consider a single machine scheduling problem. This problem has been solved for a medical laboratory. It comprises not only chain-structured precedence constraints, but also minimal and maximal times separating successive jobs in the same chain. The criterion to be minimized is the makespan. This problem arises particularly in systems where chemical processes are involved. Consider a chemical plant in which every chemical process is a sequence of chemical reactions the duration of which is upper and lower bounded. Between two successive chemical reactions which are performed in different locations, a transportation system such as robot is used to carry the product from place to place. In this kind of plant, jobs are transportation operations and production processes can be modeled as chains. Therefore the problem studied in this paper is of practical importance. We first prove that the problem is NP-complete. As a consequence, we propose heuristics for large size problems and a branch and bound based algorithm for small size problems. Computational results are reported.

Le principal but de ce travail est de proposer une étude bibliographique sur les organisations décisionnelles dédiées à la perception. De part l'importance des missions confiées à ces organisations, il est essentiel de pouvoir disposer de méthodes (analytiques ou basées sur la simulation) permettant de les valider et de les optimiser en fonction de leurs utilisations futures. Ce travail s'inscrit dans la recherche de ces méthodes. Pour cela, nous introduisons le vocabulaire des architectures distribuées et les notions fondamentales associées. Nous décrivonsensuite la modélisation des structures élémentaires des systèmes de prise de décision. Après avoir présenté les bases de la théorie de l'information, nous nous intéressons aux principales mesures de performances. Nous achevons par l'étude d'un algorithme de synthèse d'architectures et une description originale des senseurs des systèmes de perception.

Dans ce papier, nous examinons la conception des systèmes à événements discrets à l'aide des réseaux de Petri. Nous nous intéressons à la consistance, qui est une propriété souhaitée des systèmes à événements discrets. Nous mettons en évidence des conditions nécessaires et/ou suffisantes dans différents cas pour garantir la consistance. Ces conditions nous permettent de vérifier la consistance en n'examinant qu'une partie du système. A partir de ces résultats, nous développons une méthode d'aide à la conception limitée à la vérification de la propriété de consistance.

An important step when designing a Flexible Manufacturing System (FMS) using Automated Guided Vehicles (AGVs) is the definition of the number of AGVs to be used in order to reach a given productivity. A way to define this number is to consider several scenari, to define the minimal number of AGVs required by each scenario, and to keep the maximal of these numbers. In this paper, we propose a Branch and Bound (B&B) approach to define the minimal number of AGVs require for a scenario. This approach is based on an Event Graph (EG) formulation.

We consider a system composed of two independent and non-identical units. This system is under periodic inspection. Each unit is characterized by a variable whose value evolves from one inspection to the next one according to an exponential distribution. The parameters of this distribution can be different for the two units. The system breaks down if a least one of the two states exceeds a given value. These limits are referred to as breakdown limits. A preventive maintenance is applied on one unit if its state is less than the breakdown limit but exceeds a given threshold, called maintenance limit. The cost of a maintenance is much less than the cost of a repair. If a repair or a maintenance is applied on one unit, while the state of the second unit is less than the maintenance limit, a maintenance is performed on this second unit. The goal of this study is to adjust the maintenance limits to minimize the long-run average cost per unit of time. We study the probability density for the system to be in a given state. We then give the analytical expression of the cost function according to the maintenance limits. The values of these limits that minimize this function are then calculated using gradient estimation.

A heuristic procedure is developed for minimizing makespan in flow-shop scheduling problems. In comparison with current algorithms, our algorithm seems to result in an improved makespan with a small additional computational effort. An algorithm is also developed to minimize the required number of pallets for a given makespan.

In this paper, the problem of temporal aggregation in production planning is addresses. A simple facility with multiple part types is considered. The planning horizon consists of a sequence of elementary time periods and the demand for all part types is assumed to be known over these periods. The production planning problem consists of minimizing the holding and backlogging cost for all part types. Due to usual errors in demand forecasting and due to the large size of the linear programming problem commonly encountered in such problems, there is a need for aggregating the production variables over the time horizon (typically, from weekly to monthly) to result in a hierarchical structure. We consider a two-level hierarchy composing a sub-problem at each level and we propose an iterative technique which solves these sub-problems in sequence. A posteriori bounds are developed, which are useful in evaluating the performance of the iterative algorithm. Quick lower and upper bounds of the original problem are also developed. Finally, numerical results for numerous test cases are presented.

Les réseaux de Petri sont largement utilisés pour modéliser, spécifier et analyser les systèmes à événements discrets, en particulier les systèmes de production cycliques. Dans ce rapport, nous considérons un problème d'ordonnancement d'un système de production non cyclique. Les réseaux de Petri sont utilisés pour modéliser ce système. Le problème d'ordonnancement s'applique alors au franchissement des transitions. Nous proposons deux algorithmes : le premier est de type recuit simule pour recherche d'un ordonnancement proche de l'optimum, le second est une procédure par séparation et évaluation pour trouver un ordonnancement optimal.

Les réseaux de Petri sont un outil performant pour concevoir, modéliser, analyser et évaluer les systèmes a événements discrets. Dans ce rapport, nous étudions des propriétés structurelles importantes des réseaux de Petri utilises en gestion de production : la consistance et la conservation. Nous mettons en évidence une condition nécessaire et suffisante simple pour vérifier la consistance et la conservation. Cette condition permet de diminuer la dimension du problème. Nous dégageons des conditions suffisantes dans des cas particuliers. Nous proposons en outre un algorithme pour vérifier ces deux propriétés dans le cas général.

This paper addresses the problem of integration of Petri nets representing manufacturinfg systems. A modular modelling methodology being adopted, we define a class of Petri nets that characterizes a large sort of real-word manufacturing systems. These Petri nets are shown to have the properties of liveness, consistency and reversibility. We also show that the integration of such Petri nets preserves these properties under fairly weak conditions. Moreover the integrated Petri net belongs to the same Petri net class. The results obtained in this paper are expected to shed light on the design, management and control of large scale manufacturing systems where complexity problems are bound to rise and can be dealt with from the point of view of modular modelling and integration.

This paper addresses the performance evaluation and optimization of stochastic timed event graphs. The transitions firing times of such a timed event graph are random variables with general distribution. We first establish an upper bound and a lower bound for the average cycle time of the timed event graph. We prove that any cycle time greater than the greatest mean transition firing time can be reached by putting enough tokens in each place. The necessary and sufficient condition of the reachability of the greatest mean firing time is established. We then address the marking optimization problem which consists in obtaining a given cycle time while minimizing a linear criterion depending on the initial marking.

L'agencement des systèmes de fabrication est un problème complexe. Une approche en trois étapes a été récemment proposée. La première étape consiste à grouper les machines en cellules. Dans la seconde étape, on structure les cellules. Enfin, la troisième étape consiste à placer les cellules dans l'atelier. Dans ce travail, nous nous intéressons à cette troisième étape. Nous proposons une heuristique basée sur le recuit simulé, et dont l'objectif est de minimiser le critère "somme des produits (flux x distance) entre les couples de machines". La principale caractéristique de notre approche est que nous utilisons des longeurs de chemins réels comme distances entre cellules.

Ce papier est consacré a un système de production à deux niveaux qui a une cadence de fabrication élevée et un contrôle de la qualité intégré. Le niveau haut comporte une seule machine qui approvisionne alternativement les deux machines du niveau bas. Le contrôle de la qualité est implémenté à l'entrée de chaque machine du niveau bas. Ce système de production est capable de produire des pièces de types différents. L'objectif consiste à minimiser le coût total conséquence du changement d'outils au niveau haut et du rejet des lots qui contiennent au moins une pièce défectueuse. Nous étudions le cas particulier (machines identiques au niveau bas) et le cas général.

Hierarchical production planning systems attract today much attention of both management scientists and practitioners. Hierarchical production planning systems are often decomposed into three decision-making levels, i.e. a medium term level, a short term level, and a very short term level. This paper presents a medium term production planning model. At first, all machines which can perform the same operation are aggregated. Group technology is used to decompose the system into several subsystems, then specific attention is given on how to aggregate the subsystems. Similarly, parts are aggregated. We end up with an aggregate planning model involving production subsystems and part families.