We investigate the limitations of existing quantum algorithms to solve discrete optimization problems. First, we discuss the quantum counting algorithm of Brassard et al. (1998), and show that it has performance that is equivalent to that of a brute-force approach when approximating the number of valid solutions. In addition, we show that a straightforward application of Grover's algorithm (referred to as GUM by Creemers and Pérez (2023b)) dominates any quantum counting algorithm when verifying whether a valid solution exists. Next, we discuss the nested quantum search algorithm of Cerf et al. (2000), and show that it is dominated by a classical nested search that uses an approach such as GUM to find (partial) solutions to (nested) problems. Last but not least, we also discuss amplitude amplification (a procedure that generalizes Grover's algorithm), and show (once more) that it may not be possible to outperform GUM.

We present a globally optimal solution procedure to tackle the preemptive stochastic resource-constrained project scheduling problem (PSRCPSP). A solution to the PSRCPSP is a policy that allows to construct a precedence- and resource-feasible schedule that minimizes the expected makespan of a project. The PSRCPSP is an extension of the stochastic resource-constrained project scheduling problem (SRCPSP) that allows activities to be interrupted. The SRCPSP and PSRCPSP both assume that activities have stochastic durations. Even though the deterministic preemptive resource-constrained project scheduling problem (PRCPSP) has received some attention in the literature, we are the first to study the PSRCPSP. We use phase-type distributions to model the stochastic activity durations, and define a new Continuous-Time Markov Chain (CTMC) that drastically reduces memory requirements when compared to the well-known CTMC of Kulkarni and Adlakha (1986). In addition, we also propose a new and efficient approach to structure the state space of the CTMC. These improvements allow us to easily outperform the current state-of-the-art in optimal project scheduling procedures, and to solve instances of the PSPLIB J90 and J120 data sets. Last but not least, if activity durations are exponentially distributed, we show that elementary policies are globally optimal for the SRCPSP and the PSRCPSP.

We study projects with activities that have stochastic durations that are modeled using phase-type distributions. Intermediate cash flows are incurred during the execution of the project. Upon completion of all project activities a payoff is obtained. Because activity durations are stochastic, activity starting times cannot be defined at the start of the project. Instead, we have to rely on a policy to schedule activities during the execution of the project. The optimal policy schedules activities such that the expected net present value of the project is maximized. We determine the optimal policy using a new continuous-time Markov chain and a backward stochastic dynamic program. Although the new continuous-time Markov chain allows to drastically reduce memory requirements (when compared to existing methods), it also allows activities to be preempted; an assumption that is not always desirable. We demonstrate, however, that it is globally optimal not to preempt activities if certain conditions are met. A computational experiment confirms this finding. The computational experiment also shows that we significantly outperform current state-of-the-art procedures. On average, we improve computational efficiency by a factor of 600, and reduce memory requirements by a factor of 321.

We present a Markov model to approximate the queueing behavior at the G(t)/G(t)/s(t)+G(t) queue with exhaustive discipline and abandonments. The performance measures of interest are: (1) the average number of customers in queue, (2) the variance of the number of customers in queue, (3) the average number of abandonments and (4) the virtual waiting time distribution of a customer when arriving at an arbitrary moment in time. We use acyclic phase-type distributions to approximate the general interarrival, service and abandonment time distributions. An effi cient, iterative algorithm allows the accurate analysis of small- to medium-sized problem instances. The validity and accuracy of the model are assessed using a simulation study.

We study the Net Present Value (NPV) of a project with multiple stages that are executed in sequence. A cash flow (positive or negative) may be incurred at the start of each stage, and a payoff is obtained at the end of the project. The duration of a stage is a random variable with a general distribution function. For such projects, we obtain exact, closed-form expressions for the moments of the NPV, and develop a highly accurate closed-form approximation of the NPV distribution itself. In addition, we show two limit theorems that also apply in a more general context (i.e., that also apply for projects where stages are not necessarily executed in sequence). Our work has direct applications in the fields of project selection, project portfolio management, and project valuation. In addition, our work is closely related to the work of CPM/PERT, however, whereas CPM/PERT deals with project completion time, we focus on project NPV.