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
Special issue: Twelfth Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2015)
http://hdl.handle.net/2268/215728
Title: Special issue: Twelfth Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2015)
<br/>
<br/>Editor: Crama, Yves; Goossens, Dries; Leus, Roel; Schyns, Michael; Spieksma, Frits
<br/>
<br/>Abstract: This special issue of the Journal of Scheduling contains ten papers presented at the Twelfth Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2015), held from June 8 to June 12, 2015, in La Roche-en-Ardenne, Belgium.Fuzzy-Logic Controlled Genetic Algorithm for the Rail-Freight Crew-Scheduling Problem
http://hdl.handle.net/2268/215668
Title: Fuzzy-Logic Controlled Genetic Algorithm for the Rail-Freight Crew-Scheduling Problem
<br/>
<br/>Author, co-author: Khmeleva, E.; Hopgood, Adrian; Tipi, L.; Shahidan, M.
<br/>
<br/>Abstract: This article presents a fuzzy-logic controlled genetic algorithm designed for the solution of the crew-scheduling problem in the rail-freight industry. This problem refers to the assignment of train drivers to a number of train trips in accordance with complex industrial and governmental regulations. In practice, it is a challenging task due to the massive quantity of train trips, large geographical span and significant number of restrictions. While genetic algorithms are capable of handling large data sets, they are prone to stalled evolution and premature convergence on a local optimum, thereby obstructing further search. In order to tackle these problems, the proposed genetic algorithm contains an embedded fuzzy-logic controller that adjusts the mutation and crossover probabilities in accordance with the genetic algorithm's performance. The computational results demonstrate a 10% reduction in the cost of the schedule generated by this hybrid technique when compared with a genetic algorithm with fixed crossover and mutation rates.Etude socio-économique du projet de TGV FRET Liege Carex
http://hdl.handle.net/2268/214827
Title: Etude socio-économique du projet de TGV FRET Liege Carex
<br/>
<br/>Author, co-author: Lord-Tarte, E; Condé, Gilles; Devillet, GuénaëlDéveloppement d’une agriculture durable dans la commune de Xuan Quan, Viet Nam
http://hdl.handle.net/2268/213771
Title: Développement d’une agriculture durable dans la commune de Xuan Quan, Viet Nam
<br/>
<br/>Author, co-author: Nguyen Van Duy,
<br/>
<br/>Abstract: In Vietnam, agriculture field plays an important role not only in economic activities but also in cultural activities. In recent years, the fast industrialisation has a large effect on the agricultural sector. This work focuses on the Xuan Quan village, near the Red River, whose main economic activities are crop and livestock. In the last ten years, the agricultural activity was affected by two principal factors. Firstly, the urban development policy has decreased the agricultural land. Secondly, the market economy development has affected the agricultural production in trade cooperation. The Xuan Quan village takes advantage of the economic conditions which are favorable for the development of cattle. For instance, the village has a huge pasture for livestock. It is also situated closed to the commercial centres where there are high needs in beef consumption. Effectively, the cattle production takes an important place in household’s economy. However, seed supply in the village is not as much and unstable. That is the reason why the disease control is limited.
Beside the agricultural activities, the non-agricultural activities have increasingly become an important role for household. It helps farmers to earn cash quickly. Nevertheless, it also causes a labor force reduction in the agricultural field. Young generation no longer wants to participate in the agricultural sector. The traditional experiences in agriculture are at risk of loss. The agricultural production in the Xuan Quan village has many advantages but there are also many difficulties. Thus, specific policies are highly recommended to help farmers in the agricultural development towards sustainability.
<br/>
<br/>Commentary: Au Vietnam, l'agriculture joue un rôle central non seulement dans les activités économiques, mais aussi dans les activités culturelles. Ces dernières années, l'industrialisation rapide a eu un effet important sur le secteur agricole. Ce travail se focalise sur la commune de Xuan Quan, qui se situe à côté du Fleuve Rouge. L’activité économique y est principalement représentée par la culture et l'élevage. Au cours des dix dernières années, l'activité agricole a été influencée par deux facteurs principaux. Le premier est la politique de développement urbain. Les terres agricoles ont par conséquent fortement diminué. Le deuxième est le développement économique du marché, qui a influencé la production agricole dans la coopération commerciale. La commune de Xuan Quan bénéficie de conditions économiques favorables pour l’élevage du bétail. Par exemple, la commune dispose d'un énorme pâturage pour le nourrir. Il est également situé à proximité des centres commerciaux où la consommation de viande de bœuf est élevée. La production de bétail occupe une place importante dans l'économie domestique. Cependant, l'approvisionnement de semences dans le village est instable, raison pour laquelle le contrôle des maladies est limité.
Outre les activités agricoles, les activités non-agricoles ont un rôle de plus en plus important dans les ménages. Elles aident les agriculteurs à gagner de l'argent rapidement. Néanmoins, elles provoquent une réduction de la main-d'œuvre dans le domaine agricole. La jeune génération ne veut plus participer au secteur agricole. L’agriculture traditionnelle présente de grands risques de perte de production. La production agricole dans le village de Xuan Quan à de nombreux avantages, mais il y a également des difficultés. Ainsi, des politiques spécifiques sont fortement recommandées (dans ce travail) afin d’aider les agriculteurs vers le développement durable.Stochastic Inventory Routing for Perishable Products
http://hdl.handle.net/2268/213243
Title: Stochastic Inventory Routing for Perishable Products
<br/>
<br/>Author, co-author: Crama, Yves; Rezaei Sadrabadi, Mahmood; Savelsbergh, Martin; Van Woensel, Tom
<br/>
<br/>Abstract: Different solution methods are developed to solve an inventory routing problem for a perishable product with stochastic demands. The solution methods are compared empirically in terms of average profit, service level, and actual freshness. The benefits of explicitly considering demand uncertainty are quantified. The computational study highlights that in certain situations a simple ordering policy can already reach a very good performance, but that statistically and economically significant improvements are achieved when using more advanced solution methods. Managerial insights concerning the impact of shelf life and store capacity on profit are also obtained.
<br/>
<br/>Commentary: Accepted for publicationIntegration of order picking and vehicle routing in a B2C e-commerce context
http://hdl.handle.net/2268/208917
Title: Integration of order picking and vehicle routing in a B2C e-commerce context
<br/>
<br/>Author, co-author: Moons, Stef; Ramaekers, Katrien; Caris, An; Arda, Yasemin
<br/>
<br/>Abstract: E-commerce sales are increasing every year and customers who buy
goods on the Internet have high service level expectations. In order to meet these
expectations, a company’s logistics operations need to be performed carefully.
Optimizing only internal warehouse processes will often lead to suboptimal solutions.
The interrelationship between the order picking process and the delivery
process should not be ignored. Therefore, in this study, an order picking problem
and a vehicle routing problem with time windows and release dates are solved
simultaneously using a single optimization framework. To the best of our knowledge,
it is the first time that an order picking problem and a vehicle routing problem
are integrated. A mixed integer linear programming formulation for this integrated
order picking-vehicle routing problem (OP-VRP) is provided. The integrated OPVRP
is solved for small instances and the results are compared to these of an
uncoordinated approach. Computational experiments show that integration can lead
to cost savings of 14% on average. Furthermore, higher service levels can be offered
by allowing customers to request their orders later and still get delivered within the
same time windows.Integrating production scheduling and vehicle routing decisions at the operational decision level: A review and discussion
http://hdl.handle.net/2268/207442
Title: Integrating production scheduling and vehicle routing decisions at the operational decision level: A review and discussion
<br/>
<br/>Author, co-author: Moons, Stef; Ramaekers, Katrien; Caris, An; Arda, Yasemin
<br/>
<br/>Abstract: Production scheduling and vehicle routing are two well-studied problems in literature. Although these supply chain functions are interrelated, they are often solved sequentially. This uncoordinated approach can lead to suboptimal solutions. In the current competitive business environment, companies are searching for methods to save costs and improve their service level. Integrating production and distribution scheduling operations can be an approach to improve the overall performance. This paper focuses on integrated production-distribution operational level scheduling problems, which explicitly take into account vehicle routing decisions of the delivery process. Existing literature on integrated production scheduling and vehicle routing problems is reviewed and classified. Both the problem characteristics of mathematical models and the accompanying solution approaches are discussed to identify directions for further research.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 problems