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
Les problèmes “riches” de tournées de véhicules
http://hdl.handle.net/2268/203869
Title: Les problèmes “riches” de tournées de véhicules
<br/>
<br/>Author, co-author: Limbourg, SabineLa compétitivité du transport intermodal
http://hdl.handle.net/2268/203868
Title: La compétitivité du transport intermodal
<br/>
<br/>Author, co-author: Limbourg, SabineApproximation algorithms for integer covering problems via greedy column generation
http://hdl.handle.net/2268/203417
Title: Approximation algorithms for integer covering problems via greedy column generation
<br/>
<br/>Author, co-author: Crama, Yves; Van de Klundert, Joris
<br/>
<br/>Abstract: Many combinatorial optimization problems can be formulated as covering problems. In some cases, this covering formulation is not polynomial in the input size of the original problem. In order to solve the problem approximately one can apply the greedy algorithm to the covering formulation. In this case, the column generation subproblem is to determine which column the greedy algorithm chooses. This problem might be NP-hard in itself. We propose a modification of the greedy algorithm in which the column generation subproblem is solved approximately, within a factor α. We derive upper bounds for the worst case ratio of this algorithm and related polynomial approximation algorithms.Complexity of product positioning and ball intersection problems
http://hdl.handle.net/2268/203415
Title: Complexity of product positioning and ball intersection problems
<br/>
<br/>Author, co-author: Crama, Yves; Hansen, Pierre; Jaumard, Brigitte
<br/>
<br/>Abstract: The product positioning problem consists in choosing the attributes of a new product in such a way as to maximize its market share, i.e., to attract a maximum number of customers. Mathematically, the problem can be formulated as follows: given a set of balls (with respect to some norm) and a weight associated to each ball, find a point which maximizes the sum of the weights of the balls containing it. The complexity of this problem is investigated in the case of the L∞ and of the Euclidean norms. In both cases, the problem is proved to be NP-hard, but to be polynomially solvable when the dimension of the space is fixed.Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and FMS part-selection problems
http://hdl.handle.net/2268/203414
Title: Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and FMS part-selection problems
<br/>
<br/>Author, co-author: Crama, Yves; Mazzola, Joseph B.
<br/>
<br/>Abstract: This paper defines the dense subhypergraph problem (DSP), which provides a modelling framework for the nonlinear knapsack problem and other well-known problems arising in areas such as capital budgeting, flexible manufacturing system production planning, repair-kit selection, and compiler construction. We define several families of valid inequalities and state conditions under which these inequalities are facet-defining for DSP. We also explore the polyhedral structure of the cardinality-constrained DSP. Finally, we examine a special case of this problem that arises, for example, within the context of Lagrangian decomposition. For this case, we present a complete description of the convex hull of the feasible region.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.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.