ORBi Collection: Production, distribution & supply chain management
http://hdl.handle.net/2268/64
The Collection's search engineSearch this channelsearch
http://orbi.ulg.ac.be/simple-search
A column generation approach to job grouping for flexible manufacturing systems
http://hdl.handle.net/2268/204061
Title: A column generation approach to job grouping for flexible manufacturing systems
<br/>
<br/>Author, co-author: Crama, Yves; Oerlemans, Alwin G.
<br/>
<br/>Abstract: A flexible manufacturing system consists of a number of NC-machines, linked by automated material handling devices, that perform the various operations required to manufacture parts. Each operation requires different tools. These tools are stored in a limited capacity tool magazine attached to each machine. When it becomes necessary to add or remove tools from the tool magazine, the machine may have to be shut down for a setup. In this paper, we study a model which aims at minimizing the number of setups. We assume that N jobs must be processed on a machine. Each job requires a certain set of tools, which have to be present in the tool magazine of the machine when the job is executed. The magazine has a total capacity of C tools. We say that a group (subset, batch) of jobs is feasible if, together, these jobs do not require more than C tools. The job grouping problem is to partition the jobs into a minimum number of feasible groups. The problem can be formulated as a set covering problem. We solve the linear relaxation of this formulation in order to obtain tight lower bounds. Since the number of variables is potentially huge, we use a column generation approach. The column generation subproblem turns out to be NP-hard; we solve it by enumeration. We also describe some fast and simple heuristics for the job grouping problem. The result of our computational experiments is that the lower bound is extremely strong. The quality of the heuristic solutions is in general very good too. We also investigate a more general multiple-machine model in which each tool may occupy several slots in the tool magazines.Models for machine-part grouping in cellular manufacturing
http://hdl.handle.net/2268/203079
Title: Models for machine-part grouping in cellular manufacturing
<br/>
<br/>Author, co-author: Crama, Yves; Oosten, Maarten
<br/>
<br/>Abstract: For cellular manufacturing strategies to succeed, the productive system first has to be divided into highly independent cells. This means that a partition of the machines into machine groups, a partition of the parts into part families, and a matching between the machine groups and the part families have to be simultaneously determined. Mathematically, this question can be expressed as the problem of finding a near block diagonal permutation of the machine-part incidence matrix. Research on such grouping problems has primarily concentrated on the design of heuristics. Different grouping efficiency criteria have been proposed to express the quality of the groupings proposed by these heuristics. This paper is concerned with mathematical programming approaches to the formation of production cells. Existing models are reviewed and their features are briefly discussed. An alternative model is proposed, which allows for the formulation of various constraints and grouping efficiency criteria. Finally, some test problems are used to support the claim that this model may be adequate for the solution to optimality of the cell formation problem.The component retrieval problem in printed circuit board assembly
http://hdl.handle.net/2268/203078
Title: The component retrieval problem in printed circuit board assembly
<br/>
<br/>Author, co-author: Crama, Yves; Flippo, Olaf E.; Van de Klundert, Joris; Spieksma, Frits C.R.
<br/>
<br/>Abstract: The minimization of the makespan of a printed circuit board assembly process is a complex problem. Decisions involved in this problem concern the specification of the order in which components are to be placed on the board, and the assignment of component types to the feeder slots of the placement machine. If some component types are assigned to multiple feeder slots, then the additional problem emerges of selecting, for each placement on the board, the feeder slot from which the related component type is to be retrieved. In this paper, we consider this Component Retrieval Problem for placement machines that operate in a similar way as the Fuji CP II. We explain why a simple forward dynamic programming scheme cannot provide an efficient solution to this problem, thereby invalidating the correctness of an earlier published approach. We then present a polynomial algorithm that solves the problem to optimality. The analysis of the Component Retrieval Problem is greatly facilitated by its reformulation as a longest path problem in a PERT/CPM network with design aspects. Finding the minimal makespan of the assembly process thus amounts to identifying a design for which the longest path in the induced network is shortest. As an alternative interpretation, the Component Retrieval Problem can be viewed as a shortest path problem with side-constraints. The complexity of these network problems is analysed, and it is proven that the polynomial solvability of the Component Retrieval Problem is caused by the specific structure it inflicts on the arc lengths in the network. In the absence of this structure, the network problems are shown to be NP- hard in general.Inventory routing for perishable products
http://hdl.handle.net/2268/202993
Title: Inventory routing for perishable products
<br/>
<br/>Author, co-author: Rezaei Sadrabadi, Mahmood
<br/>
<br/>Abstract: We explore three problems in this thesis and develop solution methods for each problem. First, an inventory routing problem for a perishable product with stochastic demands is considered and different approximate solution methods are developed to solve. Based on computational experiments, the solution methods are compared in terms of average profit, service level, and actual freshness. The impact of relevant parameters on the performance of the solution methods is investigated. Managerial insights are drawn by analyzing the impact of shelf life and store capacity on the profit. The value of considering uncertainty and the value of accessing full information are measured. The computational results highlight that a simple ordering policy can often replace a more sophisticated solution method, while preserving the same efficacy.
Second, we introduce a vehicle routing problem (VRP) where a set of stores places deterministic orders to a logistics service provider (LSP) for two successive periods. Deliveries requested in each period can be shifted by the LSP to the other period, possibly with modified quantities. The LSP incurs a penalty for any diversion from the initial delivery period. The data regarding shifted delivery quantities and penalties are provided by the stores. From the perspective of the LSP, diversions could be beneficial if savings in the routing costs outweigh the penalties. In this work, we introduce a new two-period VRP model where the LSP seeks to improve its total cost, compared to solving two independent VRPs with fixed delivery periods, by allowing deliveries to be shifted. We solve this model to optimality by an efficient branch-and-price algorithm implementing several cutting-edge techniques. We draw algorithmic and managerial insights based on our test instances. Third, a two-period VRP is considered where the orders placed by stores for each period can be partially shifted to the other period, given that the sum of the delivery quantities in two periods to each customer is fixed. A linear penalization of delivery
shifts is assumed based on the quantity shifted. We represent two mixed integer linear programming (MILP) formulations for the problem. A column-row generation algorithm
to solve the LP-relaxation of the first formulation is developed. To solve the LP-relaxation of the second formulation, we develop a column generation algorithm. Details of two label-setting algorithms to solve the pricing problems of the column-row generation and column generation algorithms are discussed. Numerical results can be compared with a similar model in which only full delivery shifts are allowed.Scheduling jobs of equal length: complexity, facets and computational results
http://hdl.handle.net/2268/202812
Title: Scheduling jobs of equal length: complexity, facets and computational results
<br/>
<br/>Author, co-author: Crama, Yves; Spieksma, Frits C.R.
<br/>
<br/>Abstract: The following problem was originally motivated by a question arising in the automated assembly of printed circuit boards. Given aren jobs, which have to be performed on a single machine within a fixed timespan [0,T], subdivided into T unit-length subperiods. The processing time (or length) of each job equals p,p ∈ ℕ. The processing cost of each job is an arbitrary function of its start-time. The problem is to schedule all jobs so as to minimize the sum of the processing costs.
This problem is proved to be NP-hard, already for p=2 and 0–1 processing costs. On the other hand, when T=np+c, with c constant, the problem can be solved in polynomial time. A partial polyhedral description of the set of feasible solutions is presented. In particular, two classes of facet-defining inequalities are described, for which the separation problem is polynomially solvable. Also, we exhibit a class of objective functions for which the inequalities in the LP-relaxation guarantee integral solutions.
Finally, we present a simple cutting plane algorithm and report on its performance on randomly generated problem instances.Production Planning in Automated Manufacturing
http://hdl.handle.net/2268/202760
Title: Production Planning in Automated Manufacturing
<br/>
<br/>Author, co-author: Crama, Yves; Oerlemans, Alwin G.; Spieksma, Frits C.R.The assembly of printed circuit boards: A case with multiple machines and multiple board types
http://hdl.handle.net/2268/202757
Title: The assembly of printed circuit boards: A case with multiple machines and multiple board types
<br/>
<br/>Author, co-author: Crama, Yves; Flippo, Olaf E.; Van de Klundert, Joris; Spieksma, Frits C.R.
<br/>
<br/>Abstract: In this paper a typical situation arising in the assembly of printed circuit boards is investigated. The planning problem we face is how to assemble boards of different types using a single line of placement machines. From a practical viewpoint, the multiplicity of board types adds significantly to the complexity of the problem, which is already very hard to solve in the case of a single board type. In addition, relatively few studies deal with the multiple board type case. We propose a solution procedure based on a hierarchical decomposition of the planning problem. An important subproblem in this decomposition is the so-called feeder rack assignment problem. By taking into account as much as possible the individual board type characteristics (as well as the machine characteristics) we heuristically solve this problem. The remaining subproblems are solved using constructive heuristics and local search methods. The solution procedure is tested on real-life instances. It turns out that, in terms of the makespan, we can substantially improve the current solutions.Combinatorial optimization models for production scheduling in automated manufacturing systems
http://hdl.handle.net/2268/202658
Title: Combinatorial optimization models for production scheduling in automated manufacturing systems
<br/>
<br/>Author, co-author: Crama, Yves
<br/>
<br/>Abstract: Production planning and scheduling models arising in automated manufacturing environments exhibit several features not encountered in models developed for traditional production systems. For instance, models of automated facilities typically include tooling constraints which reflect the possibility for a machine to use different tools in order to perform successive operations, within limits imposed by the size of the tool magazine. Also, these models often account for the existence of flexible material handling systems whose activities must be synchronized with the machining operations in order to optimize system utilization. In this paper, we describe a few interesting combinatorial optimization problems proposed in this framework, we point to their relationships with models investigated in seemingly remote areas, and we identify a number of
challenging open problems.Neighborhood search approaches for multi-trip vehicle routing problems
http://hdl.handle.net/2268/202635
Title: Neighborhood search approaches for multi-trip vehicle routing problems
<br/>
<br/>Author, co-author: François, Véronique; Arda, Yasemin; Crama, Yves
<br/>
<br/>Abstract: We introduce two large neighborhood search approaches for solving the multi-trip vehicle routing problem (MTVRP), where each vehicle can perform several routes to serve a set of customers. The problem specifically arises when travel times between customers are short and/or when demands are large. It has been commonly solved in the literature by mixing vehicle routing heuristics and bin packing techniques aimed at assigning routes to vehicles. As an alternative, we propose specific operators that tackle the routing and the assignment aspects of the problem simultaneously. The introduced methods are compared both for the MTVRP and the version with time windows, in which the assignment part of the problem becomes more challenging. In the latter, besides considering a time window at the depot, the working time of each vehicle may not exceed a maximum duration, while its start time is a decision variable. Beyond providing several best known solutions for benchmark instances of the MTVRP, we focus on understanding the behavior of the algorithms. An automatic configuration tool is used, not only to improve the quality of the results, but also as a mean to gain knowledge about algorithm design options and their interactions. We question the impact of several heuristic components and in particular those of the roulette wheel mechanism and of the adaptive memory of routes.Cyclic scheduling of identical parts in a robotic cell
http://hdl.handle.net/2268/202512
Title: Cyclic scheduling of identical parts in a robotic cell
<br/>
<br/>Author, co-author: Crama, Yves; Van de Klundert, Joris
<br/>
<br/>Abstract: We consider a robotic flowshop in which one type of product is to be repeatedly produced and where transportation of the parts between the machines is performed by the robot. The identical parts cyclic scheduling problem is then to find a shortest cyclic schedule for the robot, i.e., a sequence of robot moves that can be repeated infinitely many times and has minimum cycle time. This problem has been solved by Sethi et al. (1992) when m <= 3. In this paper, we considerably generalize their results by proving that the identical parts cyclic scheduling problem can be solved in time polynomial in m, where m denotes the number of machines in the shop. In particular, we present a dynamic programming approach that allows to solve the problem in O(m^3) time. Our analysis heavily relies on the concept of pyramidal permutation, a concept previously investigated in connection with the traveling salesman problem.Robotic flowshop scheduling is strongly NP-complete
http://hdl.handle.net/2268/202499
Title: Robotic flowshop scheduling is strongly NP-complete
<br/>
<br/>Author, co-author: Crama, Yves; Van de Klundert, Joris
<br/>
<br/>Abstract: We consider a robotic flowshop model in which a single robot is responsible for the transportation of parts between machines and the amount of time that a part spends on a machine must be comprised in some predefined interval. The objective is to find a feasible schedule with minimal cycle time. Many researchers have proposed nonpolynomial solution methods for a variety of closely related robotic flowshop scheduling problems. This paper provides a proof that a basic version of this problem is strongly NP-Complete.Cyclic scheduling in 3-machine robotic flow shops
http://hdl.handle.net/2268/202478
Title: Cyclic scheduling in 3-machine robotic flow shops
<br/>
<br/>Author, co-author: Crama, Yves; Van de Klundert, Joris
<br/>
<br/>Abstract: We consider a robotic flow shop model in which a single robot is responsible for the transportation of parts between machines. For reasons of simplicity, when the shop is to produce a large number of identical parts, the robot usually performs repeatedly a fixed sequence of activities. This sequence of activities is called a 1-unit cycle if each execution of the sequence results in the production of exactly one part. It has been conjectured that 1-unit cycles yield optimal production rates for 3-machine robotic flow shops. We establish the validity of this conjecture.Worst-case performance of approximation algorithms for tool management problems
http://hdl.handle.net/2268/202470
Title: Worst-case performance of approximation algorithms for tool management problems
<br/>
<br/>Author, co-author: Crama, Yves; Van de Klundert, Joris
<br/>
<br/>Abstract: Since the introduction of flexible manufacturing systems, researchers have investigated various planning and scheduling problems faced by the users of such systems. Several of these problems are not encountered in more classical production settings, and so-called tool management problems appear to be among the more fundamental ones of these problems. Most tool management problems are hard to solve, so that numerous approximate solution techniques have been proposed to tackle them. In this paper, we investigate the quality of such algorithms by means of worst-case analysis. We consider several polynomial-time approximation algorithms described in the literature, and we show that all these algorithms exhibit rather poor worst-case behavior. We also study the complexity of solving tool management problems approximately. In this respect, we investigate the interrelationships among tool management problems, as well as their relationships with other well-known combinatorial problems such as the maximum clique problem or the set covering problem, and we prove several negative results on the approximability of various tool management problemsCyclic scheduling in robotic flowshops
http://hdl.handle.net/2268/202444
Title: Cyclic scheduling in robotic flowshops
<br/>
<br/>Author, co-author: Crama, Yves; Kats, Vladimir; Van de Klundert, Joris; Levner, Eugene
<br/>
<br/>Abstract: 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.Large neighborhood search for multi-trip vehicle routing
http://hdl.handle.net/2268/199416
Title: Large neighborhood search for multi-trip vehicle routing
<br/>
<br/>Author, co-author: François, Véronique; Arda, Yasemin; Crama, Yves; Laporte, Gilbert
<br/>
<br/>Abstract: We consider the multi-trip vehicle routing problem, in which each vehicle can perform several routes during the same working shift to serve a set of customers. The problem arises when customers are close to each other or when their demands are large. A common approach consists of solving this problem by combining vehicle routing heuristics with bin packing routines in order to assign routes to vehicles. We compare this approach with a heuristic that makes use of specific operators designed to tackle the routing and the assignment aspects of the problem simultaneously. Two large neighborhood search heuristics are proposed to perform the comparison. We provide insights into the configuration of the proposed algorithms by analyzing the behavior of several of their components. In particular, we question the impact of the roulette wheel mechanism. We also observe that guiding the search with an objective function designed for the multi-trip case is crucial even when exploring the solution space of the vehicle routing problem. We provide several best known solutions for benchmark instances.
<br/>
<br/>Commentary: Available online : http://www.sciencedirect.com/science/article/pii/S0377221716303034Towards sustainable food systems: the concept of agroecology and how it questions current research practices. A review
http://hdl.handle.net/2268/197503
Title: Towards sustainable food systems: the concept of agroecology and how it questions current research practices. A review
<br/>
<br/>Author, co-author: Hatt, Séverin; Artru, Sidonie; Brédart, David; Lassois, Ludivine; Francis, Frédéric; Haubruge, Eric; Garré, Sarah; Stassart, Pierre M; Dufrêne, Marc; Monty, Arnaud; Boeraeve, Fanny
<br/>
<br/>Abstract: Introduction. Multiple environmental and socio-economic indicators show that our current agriculture and the organization of the food system need to be revised. Agroecology has been proposed as a promising concept for achieving greater sustainability. This paper offers an overview and discussion of the concept based on existing literature and case studies, and explores the way it questions our current research approaches and education paradigms.
Literature. In order to improve the sustainability of agriculture, the use of external and chemical inputs needs to be minimized. Agroecological farming practices seek to optimize ecological processes, thus minimizing the need for external inputs by providing an array of ecosystem services. Implementing such practices challenges the current structure of the food system, which has been criticized for its lack of social relevance and economic viability. An agroecological approach includes all stakeholders, from field to fork, in the discussion, design and development of future food systems. This inclusion of various disciplines and stakeholders raises issues about scientists and their research practices, as well as about the education of the
next generation of scientists.
Conclusions. Agroecology is based on the concept that agricultural practices and food systems cannot be dissociated because they belong to the same natural and socio-economic context. Clearly, agroecology is not a silver-bullet, but its principles can serve as avenues for rethinking the current approaches towards achieving greater sustainability. Adapting research approaches in line with indicators that promote inter- and transdisciplinary research is essential if progress is to be made.; Introduction. De multiples indicateurs environnementaux et socio-économiques montrent que notre modèle agricole et alimentaire actuel doit être repensé. L’agroécologie a été proposée comme un concept prometteur dans le but d’accroitre sa durabilité. Cet article propose un aperçu du concept et le discute sur la base de la littérature existante et de cas d’études, et explore la manière avec laquelle il questionne notre paradigme actuel de recherche et d’enseignement.
Littérature. Dans le but d’accroitre la durabilité de l’agriculture, il est nécessaire de minimiser l’usage d’intrants externes et chimiques. Les pratiques agroécologiques cherchent à optimiser les processus écologiques permettant de limiter l’usage de ces intrants à travers la fourniture d’une diversité de services écosystémiques. L’adoption de telles pratiques bouscule le système alimentaire actuel, dont la pertinence sociale et la viabilité économique sont par ailleurs critiquées. L’agroécologie propose d’inclure l’ensemble des parties prenantes intervenant de la fourche à la fourchette dans la discussion, la conception et le développement de nos systèmes agricoles et alimentaires futurs. Cette nécessaire intégration de diverses disciplines et divers acteurs questionne les scientifiques dans leurs pratiques de recherche et d’enseignement.
Conclusions. Le concept d’agroécologie montre que nos pratiques agricoles et le système alimentaire ne peuvent pas être dissociés puisqu’ils dépendent tous les deux du contexte naturel et socio-économique dans lequel ils s’insèrent. Il apparait clairement que l’agroécologie n’est pas une solution miracle, mais que ses principes peuvent être utiles pour repenser les systèmes actuels vers plus de durabilité. Pour finir, il est essentiel que les milieux de la recherche développent des indicateurs et des environnements de travail favorisant l’inter- et la transdisciplinarité.Valeurs de l'information et performances algorithmiques pour des problèmes multi-périodes et stochastiques
http://hdl.handle.net/2268/195832
Title: Valeurs de l'information et performances algorithmiques pour des problèmes multi-périodes et stochastiques
<br/>
<br/>Author, co-author: Pironet, Thierry
<br/>
<br/>Abstract: voir documentBranch-and-Price Based Matheuristics for a Vehicle Routing Problem with Time Windows and Variable Service Start Time
http://hdl.handle.net/2268/194641
Title: Branch-and-Price Based Matheuristics for a Vehicle Routing Problem with Time Windows and Variable Service Start Time
<br/>
<br/>Author, co-author: Küçükaydın, Hande; Arda, Yasemin; Crama, Yves; Michelini, Stefano
<br/>
<br/>Abstract: We investigate a vehicle routing problem with time windows (VRPTW), where the drivers are paid per time unit worked and the starting times of their shifts are to be determined by the decision maker. In order to solve the problem to optimality, a branch-and-price (BP) algorithm is implemented recognizing the pertinent pricing subproblem as an elementary shortest path problem with resource constraints (ESPPRC) which can handle an infinite number of labels and employs effective dominance rules. We present the past, present, and future implementations of the BP procedure based on bounded bi-directional search, decremental state space relaxation, and ng-route relaxation. We further discuss the design of BP-based matheuristics which make use of metaheuristics in pricing subproblem resolution, upper bound improvement, and column generation.Recherche à voisinage large pour le problème de tournées de véhicules à voyages multiples
http://hdl.handle.net/2268/194635
Title: Recherche à voisinage large pour le problème de tournées de véhicules à voyages multiples
<br/>
<br/>Author, co-author: François, Véronique; Arda, Yasemin; Crama, Yves; Laporte, GilbertMonitoring supply chains with multivariate control charts: an economic-statistical design approach
http://hdl.handle.net/2268/194470
Title: Monitoring supply chains with multivariate control charts: an economic-statistical design approach
<br/>
<br/>Author, co-author: Heuchenne, Cédric; Faraz, Alireza; Saniga, Erwin