Testing cyber-physical systems involves the execution of test cases on target-machines equipped with the latest release of a software control system. When testing industrial robots, it is common that the target machines need to share some common resources, e.g., costly hardware devices, and so there is a need to schedule test case execution on the target machines, accounting for these shared resources. With a large number of such tests executed on a regular basis, this scheduling becomes difficult to manage manually. In fact, with manual test execution planning and scheduling, some robots may remain unoccupied for long periods of time and some test cases may not be executed.
Scheduling problems have been studied in other contexts for decades and an extensive body of research exists on resource-constrained approaches. The scheduling domain is divided into distinct areas such as process execution scheduling in operating systems and scheduling of workforces in a construction project. The scheduling problem of this paper belongs to a scheduling category named resource-constrained project scheduling problem (RCPSP; see @cite_3 @cite_14 @cite_20 for an extensive overview). RCPSP is concerned with finding schedules for resource-consuming tasks with precedence constraints in a fixed time horizon, such that the makespan is minimized @cite_20 . From the angle of RCPSP, global resources can be expressed as which are available with exactly one unit per timestep and can therefore only be consumed by a single job per timestep.
@cite_14 @cite_20 @cite_3
2140742285 1440160528 1527917700 1969848548
The resource-constrained project scheduling problem (RCPSP) consists of activities that must be scheduled subject to precedence and resource constraints such that the makespan is minimized. It has become a well-known standard problem in the context of project scheduling which has attracted numerous researchers who developed both exact and heuristic scheduling procedures. However, it is a rather basic model with assumptions that are too restrictive for many practical applications. Consequently, various extensions of the basic RCPSP have been developed. This paper gives an overview over these extensions. The extensions are classified according to the structure of the RCPSP. We summarize generalizations of the activity concept, of the precedence relations and of the resource constraints. Alternative objectives and approaches for scheduling multiple projects are discussed as well. In addition to popular variants and extensions such as multiple modes, minimal and maximal time lags, and net present value-based objectives, the paper also provides a survey of many less known concepts. Resource-constrained project scheduling with the objective of minimizing project duration (RCPSP) is one of the most studied scheduling problems. In this paper we consider the RCPSP with general temporal constraints and calendar constraints. Calendar constraints make some resources unavailable on certain days in the scheduling period and force activity execution to be delayed while resources are unavailable. They arise in practice from, e.g., unavailabilities of staff during public holidays and weekends. The resulting problems are challenging optimization problems. We develop not only four different constraint programming (CP) models to tackle the problem, but also a specialized propagator for the cumulative resource constraints taking the calendar constraints into account. This propagator includes the ability to explain its inferences so it can be used in a lazy clause generation solver. We compare these models, and different search strategies on a challenging set of benchmarks using a lazy clause generation solver. We close 83 of the open problems of the benchmark set, and show that CP solutions are highly competitive with existing Mip models of the problem. The Resource-constrained Project Scheduling Problem (Rcpsp), in which a schedule must obey the resource constraints and the precedence constraints between pairs of activities, is one of the most studied scheduling problems. An important variation of the problem (RcpspDc) is to find a schedule which maximises the net present value (discounted cash flow), when every activity has a given cash flow associated with it. Given the success of lazy clause generation (Lcg) approaches to solve Rcpsp with and without generalised precedence relations it seems worthwhile investigating Lcg's use on Rcpspdc. To do so, we must construct propagators for the net-present-value constraint that explain their propagation to the Lcg solver. In this paper we construct three different propagators for net-present-value constraints, and show how they can be used to rapidly solve RcpspDc. Resource-constrained project scheduling involves the scheduling of project activities subject to precedence and resource constraints in order to meet the objective(s) in the best possible way. The area covers a wide variety of problem types. The objective of this paper is to provide a survey of what we believe are the important recent developments in the area. Our main focus will be on the recent progress made in and the encouraging computational experience gained with the use of optimal solution procedures for the basic resource-constrained project scheduling problem (RCPSP) and important extensions. We illustrate how the branching rules, dominance and bounding arguments of a new depth- first branch-and-bound procedure can be extended to a rich variety of related problems: the generalized resource-constrained project scheduling problem, the resource-constrained project scheduling problem with generalized precedence relations, the preemptive resource-constrained project scheduling problem, the resource availability cost problem, and the resource-constrained project scheduling problem with various time resource(cost) trade-offs and discounted cash flows.