Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Proceedings of the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems ; Crama, Yves ; et al Book published by KU Leuven (2015) This volume contains abstracts of talks presented at the 12th 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 ... [more ▼] This volume contains abstracts of talks presented at the 12th 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. MAPSP is a biennial workshop dedicated to all theoretical and practical aspects of scheduling, planning, and timetabling. The abstracts in this volume include 5 invited talks by Onno Boxma, Michel Goemans, Willem-Jan van Hoeve, Rolf Niedermeier, and Stephan Westphal, plus 88 contributed talks. [less ▲] Detailed reference viewed: 98 (8 ULg)Sequential testing of k-out-of-n systems with imperfect tests ; Coolen, Kris ; et al E-print/Working paper (2015) A k-out-of-n system configuration requires that, for the overall system to be functional, at least k out of the total of n components be working. We consider the problem of sequentially testing the ... [more ▼] A k-out-of-n system configuration requires that, for the overall system to be functional, at least k out of the total of n components be working. We consider the problem of sequentially testing the components of a k-out-of-n system in order to learn the state of the system, when the tests are costly and when the individual component tests are imperfect, which means that a test can identify a component as working when in reality it is down, and vice versa. Each component is tested at most once. Since tests are imperfect, even when all components are tested the state of the system is not necessarily known with certainty, and so reaching a lower bound on the probability of correctness of the system state is used as a stopping criterion for the inspection. We define different classes of inspection policies and we examine global optimality of each of the classes. We find that a globally optimal policy for diagnosing k-out-of-n systems with imperfect tests can be found in polynomial time when the predictive error probabilities are the same for all the components. Of the three policy classes studied, the dominant policies always contain a global optimum, while elementary policies are compact in representation. The newly introduced class of so-called `interrupted block-walking' policies combines these merits of global optimality and of compactness. [less ▲] Detailed reference viewed: 31 (4 ULg)Robust optimization for resource-constrained project scheduling with uncertain activity durations ; ; Talla Nobibon, Fabrice in Flexible Services and Manufacturing Journal (2013), 25(1-2), The purpose of this paper is to propose models for project scheduling when there is considerable uncertainty in the activity durations, to the extent that the decision maker cannot with confidence ... [more ▼] The purpose of this paper is to propose models for project scheduling when there is considerable uncertainty in the activity durations, to the extent that the decision maker cannot with confidence associate probabilities with the possible scenarios. Our modeling techniques stem from robust optimization, which is a theoretical framework that enables the decision maker to produce solutions that will have a reasonably good objective value under any likely input data scenario. We develop and implement a scenario-relaxation algorithm and a scenario-relaxationbased heuristic. The first algorithm produces optimal solutions but requires excessive running times even for medium-sized instances; the second algorithm produces high-quality solutions for medium-sized instances and outperforms two benchmark heuristics. [less ▲] Detailed reference viewed: 74 (8 ULg)Complexity results and exact algorithms for robust knapsack problems Talla Nobibon, Fabrice ; Scientific conference (2011, March 04) Detailed reference viewed: 19 (0 ULg)Coloring Graphs Using Two Colors while Avoiding Monochromatic Cycles Talla Nobibon, Fabrice ; ; et al in INFORMS Journal on Computing (2011) We consider the problem of deciding whether a given directed graph can be vertex partitioned into two acyclic subgraphs. Applications of this problem include testing rationality of collective consumption ... [more ▼] We consider the problem of deciding whether a given directed graph can be vertex partitioned into two acyclic subgraphs. Applications of this problem include testing rationality of collective consumption behavior, a subject in microeconomics. We prove that the problem is NP-complete even for oriented graphs and argue that the existence of a constant-factor approximation algorithm is unlikely for an optimization version that maximizes the number of vertices that can be colored using two colors while avoiding monochromatic cycles. We present three exact algorithms—namely, an integer-programming algorithm based on cycle identification, a backtracking algorithm, and a branch-and-check algorithm. We compare these three algorithms both on real-life instances and on randomly generated graphs. We find that for the latter set of graphs, every algorithm solves instances of considerable size within a few seconds; however, the CPU time of the integer-programming algorithm increases with the number of vertices in the graph more clearly than the CPU time of the two other procedures. For real-life instances, the integer-programming algorithm solves the largest instance in about a half hour, whereas the branch-and-check algorithm takes approximately 10 minutes and the backtracking algorithm less than 5 minutes. Finally, for every algorithm, we also study empirically the transition from a high to a low probability of a YES answer as a function of the number of arcs divided by the number of vertices. [less ▲] Detailed reference viewed: 39 (1 ULg)PROJECT SCHEDULING WITH MODULAR PROJECT COMPLETION ON A BOTTLENECK RESOURCE ; ; Talla Nobibon, Fabrice et al Report (2011) In this paper, we model a research-and-development project as consisting of several modules, with each module containing one or more activities. We examine how to schedule the activities of such a project ... [more ▼] In this paper, we model a research-and-development project as consisting of several modules, with each module containing one or more activities. We examine how to schedule the activities of such a project in order to maximize the expected profit when the activities have a probability of failure and when an activity’s failure can cause its module and thereby the overall project to fail. A module succeeds when at least one of its constituent activities is successfully executed. All activities are scheduled on a scarce resource that is modeled as a single machine. We describe various policy classes, establish the relationship between the classes, develop exact algorithms to optimize over two different classes (one dynamic program and one branch-and-bound algorithm), and examine the computational performance of the algorithms on two randomly generated instance sets. [less ▲] Detailed reference viewed: 20 (2 ULg)Robust maximum weighted independent-set problems on interval graphs Talla Nobibon, Fabrice ; Report (2011) We study the maximum weighted independent-set problem on interval graphs with uncertainty on the vertex weights. We use the absolute robustness criterion and the min-max regret criterion to evaluate ... [more ▼] We study the maximum weighted independent-set problem on interval graphs with uncertainty on the vertex weights. We use the absolute robustness criterion and the min-max regret criterion to evaluate solutions. For a discrete scenario set, we nd that the problem is NP-hard for each of the robustness criteria; we also provide pseudo-polynomial time algorithms when there is a constant number of scenarios and show that the problem is strongly NP-hard when the set of scenarios is unbounded. When the scenario set is a Cartesian product, we prove that the problem is equivalent to a maximum weighted independent-set problem on the same interval graph but without uncertainty for the rst objective function and that the scenario set can be reduced for the second objective function. [less ▲] Detailed reference viewed: 31 (1 ULg) |
||