We study the computational complexity of the discrete sequential search problem with group activities, in which a set of boxes and group activities is given, and a single object is hidden in one of these boxes. The goal is to find a sequence in which the boxes are to be searched and the group...

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 must be working. This paper addresses the search for a least-cost diagnosis strategy for k-out-of-n systems when the individual component tests are imperfect,...

We study a single-machine scheduling problem that is a generalization of a number of problems for which computational procedures have already been published. Each job has a processing time, a release date, a due date, a deadline and a weight representing the penalty per unit-time delay beyond...

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 outcomes of a decision.Our modeling techniques stem from...

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...

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 fi nd that the problem is NP-hard for each of the...

This paper studies the robust knapsack problem, for which solutions are, up to a certain point, immune to data uncertainty. We complement the works found in the literature where uncertainty affects only the profits or only the weights of the items by studying the complexity and approximation of...

This paper develops an optimization model that captures the annual planning of product-targeting campaigns occurring in fi nancial institutions. The formulation described in this paper extends current product-targeting optimization models found in the literature on two main aspects, namely the...

This article describes a heuristic for scheduling so-called ‘modular' projects. Exact solutions to this NP-hard problem can be obtained with existing branch-and-bound and dynamic-programming algorithms, but only for small to medium-size instances. The proposed heuristic, by contrast, can be...

We study the stochastic resource-constrained project scheduling problem or SRCPSP, where project activities have stochastic durations. A solution is a scheduling policy, and we propose a new class of policies that is a generalization of most of the classes described in the literature. A policy...