References of "Spieksma, Frits C.R"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailRevealed preference tests of collectively rational consumption behavior: formulations and algorithms
Talla Nobibon, Fabrice; Cherchye, Laurens; Crama, Yves ULg et al

in Operations Research (2016), 64(6), 11971216

This paper focuses on revealed preference tests of the collective model of household consumption. We start by showing that the decision problems corresponding to testing collective rationality are {\sc np ... [more ▼]

This paper focuses on revealed preference tests of the collective model of household consumption. We start by showing that the decision problems corresponding to testing collective rationality are {\sc np}-complete. This makes the application of these tests problematic for (increasingly available) large(r) scale data sets. We then present two approaches to overcome this negative result. First, we introduce exact algorithms based on mixed-integer programming ({\sc mip}) formulations of the collective rationality tests, which can be usefully applied to medium sized data sets. Next, we propose simulated annealing heuristics, which allow for efficient testing of the collective model in the case of large data sets. We illustrate our methods by a number of computational experiments based on Dutch labor supply data. [less ▲]

Detailed reference viewed: 108 (12 ULg)
Full Text
Peer Reviewed
See detailMulti-Dimensional Vector Assignment Problems
Dokka, Trivikram; Crama, Yves ULg; Spieksma, Frits C.R.

in Discrete Optimization (2014), 14

We consider a special class of axial multi-dimensional assignment problems called multi- dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by m disjoint sets, each of ... [more ▼]

We consider a special class of axial multi-dimensional assignment problems called multi- dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by m disjoint sets, each of which contains the same number n of p-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an m-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the m sets of vectors into n m-tuples so that no two vectors from the same set are in the same m-tuple and so that the sum of the costs of the m-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider a particular class of polynomial-time heuristics for MVA, namely the sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, sequential heuristics have a finite approximation ratio for every fixed m. Moreover, we establish smaller approximation ratios when the cost function is submodular and, for a specific sequential heuristic, when the cost function is additive. We provide examples to illustrate the tightness of our analysis. Furthermore, we show that the MVA problem is APX-hard even for the case m = 3 and for binary input vectors. Finally, we show that the problem can be solved in polynomial time in the special case of binary vectors with fixed dimension p. [less ▲]

Detailed reference viewed: 47 (9 ULg)
Full Text
See detailApproximation Algorithms for Multi-Dimensional Vector Assignment Problems
Dokka, Trivikram; Crama, Yves ULg; Spieksma, Frits C.R.

E-print/Working paper (2013)

We consider a special class of axial multi-dimensional assignment problems called multi-dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by $m$ disjoint sets, each ... [more ▼]

We consider a special class of axial multi-dimensional assignment problems called multi-dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by $m$ disjoint sets, each of which contains the same number $n$ of $p$-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an $m$-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the $m$ sets of vectors into $n$ $m$-tuples so that no two vectors from the same set are in the same $m$-tuple and so that the total cost of the $m$-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider two classes of polynomial-time heuristics for MVA, namely, hub heuristics and sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, hub heuristics, as well as sequential heuristics, have finite approximation ratio for every fixed $m$. Moreover, we establish better approximation ratios for certain variants of hub heuristics and sequential heuristics when the cost function is monotone and submodular, or when it is additive. We provide examples to illustrate the tightness of our analysis. Furthermore, we show that the MVA problem is APX-hard even for the case $m=3$ and for binary input vectors. Finally, we show that the problem can be solved in polynomial time in the special case of binary vectors with fixed dimension $p$. [less ▲]

Detailed reference viewed: 145 (11 ULg)
Full Text
Peer Reviewed
See detailThe interval ordering problem
Durr, Christophe; Queyranne, Maurice; Spieksma, Frits C.R. et al

in Discrete Applied Mathematics (2012)

Detailed reference viewed: 12 (0 ULg)
Full Text
Peer Reviewed
See detailCounting and enumerating aggregate classifiers
Adem, Jan; Crama, Yves ULg; Gochet, Willy et al

in Discrete Applied Mathematics (2008), 156(3), 2459-2468

We propose a generic model for the "weighted voting" aggregation step performed by several methods in supervised classification. Further, we construct an algorithm to count the number of distinct ... [more ▼]

We propose a generic model for the "weighted voting" aggregation step performed by several methods in supervised classification. Further, we construct an algorithm to count the number of distinct aggregate classifiers that arise in this model. When there are only two classes in the classification problem, we show that a class of functions that arises from aggregate classifiers coincides with the class of self-dual positive threshold Boolean functions. [less ▲]

Detailed reference viewed: 48 (14 ULg)
Full Text
Peer Reviewed
See detailThe tool switching problem revisited
Crama, Yves ULg; Moonen, Linda S; Spieksma, Frits CR et al

in European Journal of Operational Research (2007), 182(2), 952-957

In this note we study the tool switching problem with non-uniform tool sizes. More specifically, we consider the problem where the job sequence is given as part of the input. We show that the resulting ... [more ▼]

In this note we study the tool switching problem with non-uniform tool sizes. More specifically, we consider the problem where the job sequence is given as part of the input. We show that the resulting tooling problem is strongly N P-complete, even in case of unit loading and unloading costs. On the other hand, if the capacity of the tool magazine is also given as part of the input, we show that the problem is solvable in polynomial time. These results settle the complexity of a relevant variant of the tool switching problem. (C) 2006 Elsevier B.V. All rights reserved. [less ▲]

Detailed reference viewed: 43 (6 ULg)
Full Text
Peer Reviewed
See detailProduction planning problems in printed circuit board assembly
Crama, Yves ULg; van de Klundert, Joris; Spieksma, Frits CR

in Discrete Applied Mathematics (2002), 123(1-3), 339-361

This survey describes some of the main optimization problems arising in the context of production planning for the assembly of printed circuit boards. The discussion is structured around a hierarchical ... [more ▼]

This survey describes some of the main optimization problems arising in the context of production planning for the assembly of printed circuit boards. The discussion is structured around a hierarchical decomposition of the planning process into distinct optimization subproblems, addressing issues such as the assignment of board types to machine groups, the allocation of component feeders to individual machines, the determination of optimal production sequences, etc, The paper reviews the literature on this topic with an emphasis on the most recent developments, on the fundamental structure of the mathematical models and on the relation between these models and some 'environmental' variables such as the layout of the shop or the product mix. (C) 2002 Elsevier Science B.V, All rights reserved. [less ▲]

Detailed reference viewed: 388 (7 ULg)
Full Text
Peer Reviewed
See detailThe assembly of printed circuit boards: A case with multiple machines and multiple board types
Crama, Yves ULg; Flippo, Olaf E.; Van de Klundert, Joris et al

in European Journal of Operational Research (1997), 98

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 17 (2 ULg)
Full Text
Peer Reviewed
See detailThe component retrieval problem in printed circuit board assembly
Crama, Yves ULg; Flippo, Olaf E.; Van de Klundert, Joris et al

in International Journal of Flexible Manufacturing Systems (1996), 8

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 27 (1 ULg)
Peer Reviewed
See detailScheduling jobs of equal length: complexity, facets and computational results
Crama, Yves ULg; Spieksma, Frits C.R.

in Mathematical Programming (1996), 72

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 16 (3 ULg)
See detailProduction Planning in Automated Manufacturing
Crama, Yves ULg; Oerlemans, Alwin G.; Spieksma, Frits C.R.

Book published by Springer Science & Business Media B.V. - Second, revised and enlarged edition. (First edition: 1994) (1996)

Detailed reference viewed: 22 (1 ULg)
See detailProduction Planning in Automated Manufacturing
Crama, Yves ULg; Oerlemans, Alwin G.; Spieksma, Frits C.R.

Book published by Springer-Verlag - First edition. (Second, revised and enlarged edition: 1996) (1994)

Detailed reference viewed: 72 (18 ULg)
Full Text
See detailThe complexity of scheduling short tasks with few starting times
Crama, Yves ULg; Spieksma, Frits C.R.

Report (1992)

The following problem is proved to be NP-complete: given n tasks, such that each task has processing time \tau=2, and has no more than k=3 possible starting times, does there exist a feasible schedule for ... [more ▼]

The following problem is proved to be NP-complete: given n tasks, such that each task has processing time \tau=2, and has no more than k=3 possible starting times, does there exist a feasible schedule for these tasks on a single processor? This result establishes a sharp borderline between NP-complete and polynomially solvable versions of this problem with respect to the parameters \tau and k. [less ▲]

Detailed reference viewed: 41 (1 ULg)