Resource-Constrained Project Scheduling with Project Management Information Systems

Most commercial project management software packages include planning methods to devise schedules for resource-constrained projects. As it is proprietary information of the software vendors which planning methods are implemented, the question arises how the software packages differ in quality with respect to their resource-allocation capabilities. We experimentally evaluate the resource-allocation capabilities of eight recent software packages by using 1,560 instances with 30, 60, and 120 activities of the well-known PSPLIB library. In some of the analyzed packages, the user may influence the resource allocation by means of multi-level priority rules, whereas in other packages, only few options can be chosen. We study the impact of various complexity parameters and priority rules on the project duration obtained by the software packages. The results indicate that the resource-allocation capabilities of these packages differ significantly. In general, the relative gap between the packages gets larger with increasing resource scarcity and with increasing number of activities. Moreover, the selection of the priority rule has a considerable impact on the project duration. Surprisingly, when selecting a priority rule in the packages where it is possible, both the mean and the variance of the project duration are in general worse than for the packages which do not offer the selection of a priority rule.

The Resource-Constrained Project Scheduling Problem with Work-Content Constraints

For executing the activities of a project, one or several resources are required, which are in general scarce. Many resource-allocation methods assume that the usage of these resources by an activity is constant during execution; in practice, however, the project manager may vary resource usage by individual activities over time within prescribed bounds. This variation gives rise to the project scheduling problem which consists in allocating the scarce resources to the project activities over time such that the project duration is minimized, the total number of resource units allocated equals the prescribed work content of each activity, and precedence and various work-content-related constraints are met.

4D/3D reduction of dualities: mirrors on the circle

We engineer a brane picture for the reduction of Seiberg dualities from 4D to 3D, valid also in the presence of orientifold planes. We obtain effective 3D dualities on the circle by T-duality, geometrizing the non-perturbative superpotential which is an affine Toda potential. When reducing to pure 3D, we define a double-scaling limit which creates a sector of interacting singlets, giving a unified mechanism for the brane reduction of dualities.

On an Application of Microsoft Excel’s Evolutionary Solver to the Resource-Constrained Project Scheduling Problem RCPSP

The Solver Add-in of Microsoft Excel is widely used in courses on Operations Research and in industrial applications. Since the 2010 version of Microsoft Excel, the Solver Add-in comprises a so-called evolutionary solver. We analyze how this metaheuristic can be applied to the resource-constrained project scheduling problem (RCPSP). We present an implementation of a schedule-generation scheme in a spreadsheet, which combined with the evolutionary solver can be used for devising good feasible schedules. Our computational results indicate that using this approach, non-trivial instances of the RCPSP can be (approximately) solved to optimality.

An MILP-based heuristic for staff scheduling problems with acceptance levels

We present a real-world staff-assignment problem that was reported to us by a provider of an online workforce scheduling software. The problem consists of assigning employees to work shifts subject to a large variety of requirements related to work laws, work shift compatibility, workload balancing, and personal preferences of employees. A target value is given for each requirement, and all possible deviations from these values are associated with acceptance levels. The objective is to minimize the total number of deviations in ascending order of the acceptance levels. We present an exact lexicographic goal programming MILP formulation and an MILP-based heuristic. The heuristic consists of two phases: in the first phase a feasible schedule is built and in the second phase parts of the schedule are iteratively re-optimized by applying an exact MILP model. A major advantage of such MILP-based approaches is the flexibility to account for additional constraints or modified planning objectives, which is important as the requirements may vary depending on the company or planning period. The applicability of the heuristic is demonstrated for a test set derived from real-world data. Our computational results indicate that the heuristic is able to devise optimal solutions to non-trivial problem instances, and outperforms the exact lexicographic goal programming formulation on medium- and large-sized problem instances.

Efficient list-generation techniques for scheduling assessment centers

Human resources managers often conduct assessment centers to evaluate candidates for a job position. During an assessment center, the candidates perform a series of tasks. The tasks require one or two assessors (e.g., managers or psychologists) that observe and evaluate the candidates. If an exercise is designed as a role-play, an actor is required who plays, e.g., an unhappy customer with whom the candidate has to deal with. Besides performing the tasks, each candidate has a lunch break within a prescribed time window. Each candidate should be observed by approximately half the number of the assessors; however, an assessor may not observe a candidate if they personally know each other. The planning problem consists of determining (1) resource-feasible start times of all tasks and lunch breaks and (2) a feasible assignment of assessors to candidates, such that the assessment center duration is minimized. We present a list-scheduling heuristic that generates feasible schedules for such assessment centers. We propose several novel techniques to generate the respective task lists. Our computational results indicate that our approach is capable of devising optimal or near-optimal schedules for real-world instances within short CPU time.

A heuristic approach for scheduling assessment centers

Human resources managers often use assessment centers to evaluate candidates for a job position. During an assessment center, the candidates perform a series of exercises. The exercises require one or two assessors (e.g., managers or psychologists) that observe and evaluate the candidate. If an exercise is designed as a role-play, an actor is required as well which plays, e.g., an unhappy customer with whom the candidate has to deal with. Besides performing the exercises, the candidates have a lunch break within a prescribed time window. Each candidate should be observed by approximately half the number of the assessors. Moreover, an assessor cannot be assigned to a candidate if they personally know each other. The planning problem consists of determining (1) resource-feasible start times of all exercises and lunch breaks and (2) a feasible assignment of assessors to candidates, such that the assessment center duration is minimized. We propose a list-scheduling heuristic that generates feasible schedules for such assessment centers. We develop novel procedures for devising an appropriate scheduling list and for incorporating the problem-specific constraints. Our computational results indicate that our approach is capable of devising optimal or near-optimal solutions to real-world instances within short CPU time.

Noninvasive 4D pressure difference mapping derived from 4D flow MRI in patients with repaired aortic coarctation: comparison with young healthy volunteers

To assess spatial and temporal pressure characteristics in patients with repaired aortic coarctation compared to young healthy volunteers using time-resolved velocity-encoded three-dimensional phase-contrast magnetic resonance imaging (4D flow MRI) and derived 4D pressure difference maps. After in vitro validation against invasive catheterization as gold standard, 4D flow MRI of the thoracic aorta was performed at 1.5T in 13 consecutive patients after aortic coarctation repair without recoarctation and 13 healthy volunteers. Using in-house developed processing software, 4D pressure difference maps were computed based on the Navier-Stokes equation. Pressure difference amplitudes, maximum slope of pressure amplitudes and spatial pressure range at mid systole were retrospectively measured by three readers, and twice by one reader to assess inter- and intraobserver agreement. In vitro, pressure differences derived from 4D flow MRI showed excellent agreement to invasive catheter measurements. In vivo, pressure difference amplitudes, maximum slope of pressure difference amplitudes and spatial pressure range at mid systole were significantly increased in patients compared to volunteers in the aortic arch, the proximal descending and the distal descending thoracic aorta (p < 0.05). Greatest differences occurred in the proximal descending aorta with values of the three parameters for patients versus volunteers being 19.7 ± 7.5 versus 10.0 ± 2.0 (p < 0.001), 10.9 ± 10.4 versus 1.9 ± 0.4 (p = 0.002), and 8.7 ± 6.3 versus 1.6 ± 0.9 (p < 0.001). Inter- and intraobserver agreements were excellent (p < 0.001). Noninvasive 4D pressure difference mapping derived from 4D flow MRI enables detection of altered intraluminal aortic pressures and showed significant spatial and temporal changes in patients with repaired aortic coarctation.

Improving 4D plan quality for PBS-based liver tumour treatments by combining online image guided beam gating with rescanning.

Pencil beam scanned (PBS) proton therapy has many advantages over conventional radiotherapy, but its effectiveness for treating mobile tumours remains questionable. Gating dose delivery to the breathing pattern is a well-developed method in conventional radiotherapy for mitigating tumour-motion, but its clinical efficiency for PBS proton therapy is not yet well documented. In this study, the dosimetric benefits and the treatment efficiency of beam gating for PBS proton therapy has been comprehensively evaluated. A series of dedicated 4D dose calculations (4DDC) have been performed on 9 different 4DCT(MRI) liver data sets, which give realistic 4DCT extracting motion information from 4DMRI. The value of 4DCT(MRI) is its capability of providing not only patient geometries and deformable breathing characteristics, but also includes variations in the breathing patterns between breathing cycles. In order to monitor target motion and derive a gating signal, we simulate time-resolved beams' eye view (BEV) x-ray images as an online motion surrogate. 4DDCs have been performed using three amplitude-based gating window sizes (10/5/3 mm) with motion surrogates derived from either pre-implanted fiducial markers or the diaphragm. In addition, gating has also been simulated in combination with up to 19 times rescanning using either volumetric or layered approaches. The quality of the resulting 4DDC plans has been quantified in terms of the plan homogeneity index (HI), total treatment time and duty cycle. Results show that neither beam gating nor rescanning alone can fully retrieve the plan homogeneity of the static reference plan. Especially for variable breathing patterns, reductions of the effective duty cycle to as low as 10% have been observed with the smallest gating rescanning window (3 mm), implying that gating on its own for such cases would result in much longer treatment times. In addition, when rescanning is applied on its own, large differences between volumetric and layered rescanning have been observed as a function of increasing number of re-scans. However, once gating and rescanning is combined, HI to within 2% of the static plan could be achieved in the clinical target volume, with only moderately prolonged treatment times, irrespective of the rescanning strategy used. Moreover, these results are independent of the motion surrogate used. In conclusion, our results suggest image guided beam gating, combined with rescanning, is a feasible, effective and efficient motion mitigation approach for PBS-based liver tumour treatments.

Temporally Coherent Disparity Maps Using CRFs with Fast 4D Filtering

State of the art methods for disparity estimation achieve good results for single stereo frames, but temporal coherence in stereo videos is often neglected. In this paper we present a method to compute temporally coherent disparity maps. We define an energy over whole stereo sequences and optimize their Conditional Random Field (CRF) distributions using mean-field approximation. We introduce novel terms for smoothness and consistency between the left and right views, and perform CRF optimization by fast, iterative spatio-temporal filtering with linear complexity in the total number of pixels. Our results rank among the state of the art while having significantly less flickering artifacts in stereo sequences.