ORBi Collection: Quantitative methods in economics & management
http://hdl.handle.net/2268/71
The Collection's search engineSearch this channelsearch
http://orbi.ulg.ac.be/simple-search
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 polytope of block diagonal matrices and complete bipartite partitionings
http://hdl.handle.net/2268/202758
Title: The polytope of block diagonal matrices and complete bipartite partitionings
<br/>
<br/>Author, co-author: Crama, Yves; Oosten, Maarten
<br/>
<br/>Abstract: Motivated by a fundamental clustering problem arising in several areas (production management, marketing, numerical analysis, etc.), we investigate the facial structure of the polytope whose extreme points are all 0–1 block diagonal matrices. For this polytope, general properties of facet-defining inequalities are investigated and specific families of facets are identified. Various techniques for lifting or combining facet-defining inequalities into new ones are also presented. Throughout the paper, a block diagonal matrix is regarded as the adjacency matrix of a disjoint union of complete bipartite graphs. The presentation and the derivation of the results heavily rely on this graph-theoretic interpretation.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.Hitting or avoiding balls in Euclidean space
http://hdl.handle.net/2268/202636
Title: Hitting or avoiding balls in Euclidean space
<br/>
<br/>Author, co-author: Crama, Yves; Ibaraki, Toshihide
<br/>
<br/>Abstract: We investigate the algorithmic complexity of several geometric problems of the following type: given a "feasible" box and a collection of balls in Euclidean space, find a feasible point which is covered by as few or, respectively, by as many balls as possible. We establish that all these problems are NP-hard in their most general version. We derive tight lower and upper bounds on the complexity of their one-dimensional versions. Finally, we show that all these problems can be solved in polynomial time when the dimension of the space is fixed.Variable and term removal from Boolean formulae
http://hdl.handle.net/2268/202634
Title: Variable and term removal from Boolean formulae
<br/>
<br/>Author, co-author: Crama, Yves; Ekin, Oya; Hammer, Peter L.
<br/>
<br/>Abstract: Given a Boolean formula in disjunctive normal form, the variable deletion control set problem consists in finding a minimum cardinality set of variables whose deletion from the formula results in a DNF satisfying some prescribed property. Similar problems can be defined with respect to the fixation of variables or the deletion of terms in a DNF. In this paper, we investigate the complexity of such problems for a broad class of DNF properties.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.Corporate control concentration measurement and firm performance
http://hdl.handle.net/2268/202423
Title: Corporate control concentration measurement and firm performance
<br/>
<br/>Author, co-author: Crama, Yves; Leruth, Luc; Renneboog, Luc; Urbain, Jean-Pierre
<br/>
<br/>Abstract: Traditionally share price returns and their variance have been explained by factors linked to the operations of the company such as systematic risk, corporate size and P/E ratios or by factors related to the influence of the macro-economic environment. In these models, the institutional environment in terms of concentration and nature of voting rights, bank debt dependence and corporate and legal mechanisms to change control have rarely been included. In this paper we have a dual objective. We first highlight the large discrepancies among
corporate governance environments. We conclude that there is a need for a theoretically well-grounded measure of corporate control applicable to all systems and we define such a measure. Secondly, the impact of ownership structure on the share price performance and corporate risk is empirically analysed for companies listed on the London Stock Exchange. Within Europe, the UK corporate landscape is particularly interesting because of its widely-held nature and the liquidity of the market for controlling rights. Our results point to the fact that voting power, as measured by Z-indices, is tightly correlated to both share price performance and risk. The negative relation between the largest Z-index and corporate share price performance is explained by the fact that the voting power held by executive directors measures the degree of insider entrenchment which has a negative impact on performance. This negative relation is compensated when outside shareholders (e.g. industrial companies, individuals or families) own substantial voting power and may actively monitor the firm. This is because with a counterbalancing pole of control, the largest shareholder is forced to compromise and maximize firm’s profits rather than his or her own utility function. The risk regressions show that entrenched insider as well as large shareholders my seek higher levels
of systematic risk. It may be that these shareholders prefer risky high growth strategies which are providing higher levels of private benefits for these types of shareholders at the expense of small shareholders. We also conclude that the classic Herfindahl indices
inaccurately measure control, which is reflected in the weaker relationship with performance.Column Generation Based Algorithms for a VRP with Time Windows and Variable Departure Times
http://hdl.handle.net/2268/202357
Title: Column Generation Based Algorithms for a VRP with Time Windows and Variable Departure Times
<br/>
<br/>Author, co-author: Michelini, Stefano; Arda, Yasemin; Küçükaydin, Hande
<br/>
<br/>Abstract: We investigate a solution methodology for a variant of the VRP with time windows. In the examined variant, the departure time of each vehicle from the depot can be determined by the decision-maker, who aims at minimizing the overall duration of the routes, including waiting times, while respecting the maximum allowed working duration of each vehicle. In order to solve this problem with a branch-and-price methodology, we address the associated pricing problem as an elementary shortest path problem with resource constraints (ESPPRC). We propose an adapted bidirectional dynamic programming algorithm for the studied ESPPRC. The decremental state space relaxation (DSSR) technique is also implemented as an acceleration technique both to obtain ng-routes and elementary routes. Several implementation and integration strategies are considered for the DSSR and ng-route relaxation techniques. The ng-route pricing and the elementary route pricing algorithms are compared inside a column generation procedure. For both column generation procedures, the algorithmic choices are made and the values of the numerical parameters are determined using an automatic algorithm configuration tool, the irace package. Finally, we discuss how these column generation procedures can be included as a component in the development of a matheuristic.A Bilevel Design and Pricing Model for an Intermodal Service Network
http://hdl.handle.net/2268/202235
Title: A Bilevel Design and Pricing Model for an Intermodal Service Network
<br/>
<br/>Author, co-author: Tawfik, Christine Maher Fouad; Limbourg, Sabine
<br/>
<br/>Abstract: This work addresses the problem of jointly designing and pricing intermodal freight services during a medium-term planning horizon. Given the innate hierarchy in the problem, a bilevel program is considered where, at the upper level, an intermodal service provider seeks to maximize his profit through selecting the frequencies of his services and their associated prices, while at the lower level, target shipper firms choose to send their demands among the offered intermodal itineraries and the always available trucking competition.Early detection of university students in potential difficulty
http://hdl.handle.net/2268/201648
Title: Early detection of university students in potential difficulty
<br/>
<br/>Author, co-author: Hoffait, Anne-Sophie; Schyns, MichaelBalanced words and related concepts: applications and complexity issues
http://hdl.handle.net/2268/201448
Title: Balanced words and related concepts: applications and complexity issues
<br/>
<br/>Author, co-author: Crama, Yves
<br/>
<br/>Abstract: In this talk, I present a few results and several questions about "regular" sequences of integers
and related concepts, such as balanced words, partitions and covers of the integers by
arithmetic sequences. Such concepts have been investigated in pure mathematics, but also
naturally arise in a variety of application fields such as production planning, political science, or
queueing theory. I briefly present some of these applications and explain how they motivate
seemingly new questions relating, for instance, to the algorithmic complexity of regular partitions, or to the structure of balanced words.
The presentation is based on joint work with Nadia Brauner and Vincent Jost (Grenoble).LARCH: A package for estimating multinomial, nested, and cross-nested logit models that account for semi-aggregate data
http://hdl.handle.net/2268/201287
Title: LARCH: A package for estimating multinomial, nested, and cross-nested logit models that account for semi-aggregate data
<br/>
<br/>Author, co-author: Newman, Jeffrey; Lurkin, Virginie; Garrow, Laurie
<br/>
<br/>Abstract: We present a summary of important computational issues and opportunities that arise from
the use of semi-aggregate data (where the explanatory data for choice scenarios are not necessarily unique for each decision-maker) in discrete choice models. This data feature is commonly encountered with large transactional databases that have limited consumer information, such as itinerary choice modeling. We developed a software package called Larch, written in Python and C++, to take advantage of this kind of data to greatly speed the estimation of discrete choice model parameters. Benchmarking experiments against Stata (a commonly used commercial package) and Biogeme (a commonly used freeware package) based on an industry dataset for airline itinerary choice modeling applications shows that the size of the input estimation files are 50 to 100 times larger in Stata and Biogeme, respectively. Estimation times are also much faster in Larch; e.g., for a small itinerary choice problem, a multinomial logit model estimated in Larch converged in less than one second whereas the same model took almost 15 seconds in Stata and more than three minutes in Biogeme. For more complex discrete choice models, such as the ordered generalized extreme value model, estimation times were two seconds in Larch and four to five days in Biogeme.Reformulations of nonlinear binary optimization problems
http://hdl.handle.net/2268/200986
Title: Reformulations of nonlinear binary optimization problems
<br/>
<br/>Author, co-author: Crama, YvesOptimal returnable transport items management
http://hdl.handle.net/2268/200983
Title: Optimal returnable transport items management
<br/>
<br/>Author, co-author: Limbourg, Sabine; Martin, Adeline; Paquay, Célia
<br/>
<br/>Abstract: Reducing environmental impact, related regulations and potential for operational benefits are the main reasons why companies share their returnable transport items (RTIs) among the different partners of a closed-loop supply chain. Face-to-face interviews with senior executives from seven companies involved in RTIs were conducted to gain a thorough understanding of how they manage the flow of RTIs as well as how they determine the number of RTIs needed in a fleet. Results indicate that RTIs managements are quite diverse, that some common beliefs about RTIs do not apply to all RTI types, and that research efforts are needed in the areas of RTI acquisition; warehouse layout, inventory routing problem; production planning and control; tracking and scheduling.