A mixed-integer linear programming approach to the optimization of event-bus schedules: a scheduling application in the tourism sector

This paper deals with “The Enchanted Journey,” which is a daily event tour booked by Bollywood-film fans. During the tour, the participants visit original sites of famous Bollywood films at various locations in Switzerland; moreover, the tour includes stops for lunch and shopping. Each day, up to five buses operate the tour. For operational reasons, however, two or more buses cannot stay at the same location simultaneously. Further operative constraints include time windows for all activities and precedence constraints between some activities. The planning problem is how to compute a feasible schedule for each bus. We implement a two-step hierarchical approach. In the first step, we minimize the total waiting time; in the second step, we minimize the total travel time of all buses. We present a basic formulation of this problem as a mixed-integer linear program. We enhance this basic formulation by symmetry-breaking constraints, which reduces the search space without loss of generality. We report on computational results obtained with the Gurobi Solver. Our numerical results show that all relevant problem instances can be solved using the basic formulation within reasonable CPU time, and that the symmetry-breaking constraints reduce that CPU time considerably.

Towards Faster Method Search Through Static Ecosystem Analysis

Software developers are often unsure of the exact name of the method they need to use to invoke the desired behavior in a given context. This results in a process of searching for the correct method name in documentation, which can be lengthy and distracting to the developer. We can decrease the method search time by enhancing the documentation of a class with the most frequently used methods. Usage frequency data for methods is gathered by analyzing other projects from the same ecosystem - written in the same language and sharing dependencies. We implemented a proof of concept of the approach for Pharo Smalltalk and Java. In Pharo Smalltalk, methods are commonly searched for using a code browser tool called "Nautilus", and in Java using a web browser displaying HTML based documentation - Javadoc. We developed plugins for both browsers and gathered method usage data from open source projects, in order to increase developer productivity by reducing method search time. A small initial evaluation has been conducted showing promising results in improving developer productivity.

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.

Proposals for Specific Activities of the Basic Mandate and Priority Action Projects, 2nd round 2005: Documentation for the ESAPP Advisory Board Meeting of June 15th, 2005

Budget frame-figures for 2nd half 2005; priority listing of proposals for PAP 2nd round 2005; evaluation sheets of approved, revised and rejected proposals for Specific Activities of the BM and PAP.

Annual Planning for the Basic Mandate and Proposals for Priority Action Projects, 1st round 2005

Budget frame-figures for 2005; annual planning for the BM 2005; priority listing of proposals for PAP 2005; evaluation sheets of approved, postponed and rejected proposals for the BM and PAP.

Proposals for Priority Action Projects, second round 2004

Budget frame-figures for 2nd half of 2004; priority listing of proposals for PAP 2nd round 2004; evaluation sheets of approved, revised and rejected proposals for PAP.

Nonlinear quasi-static finite element simulations predict in vitro strength of human proximal femora assessed in a dynamic sideways fall setup

Osteoporotic proximal femur fractures are caused by low energy trauma, typically when falling on the hip from standing height. Finite element simulations, widely used to predict the fracture load of femora in fall, usually include neither mass-related inertial effects, nor the viscous part of bone's material behavior. The aim of this study was to elucidate if quasi-static non-linear homogenized finite element analyses can predict in vitro mechanical properties of proximal femora assessed in dynamic drop tower experiments. The case-specific numerical models of thirteen femora predicted the strength (R2=0.84, SEE=540 N, 16.2%), stiffness (R2=0.82, SEE=233 N/mm, 18.0%) and fracture energy (R2=0.72, SEE=3.85 J, 39.6%); and provided fair qualitative matches with the fracture patterns. The influence of material anisotropy was negligible for all predictions. These results suggest that quasi-static homogenized finite element analysis may be used to predict mechanical properties of proximal femora in the dynamic sideways fall situation.

Excitonic splittings in molecular dimers: why static ab initio calculations cannot match them

After decades of research on molecular excitons, only few molecular dimers are available on which exciton and vibronic coupling theories can be rigorously tested. In centrosymmetric H-bonded dimers consisting of identical (hetero)aromatic chromophores, the monomer electronic transition dipole moment vectors subtract or add, yielding S0 → S1 and S0 → S2 transitions that are symmetry-forbidden or -allowed, respectively. Symmetry breaking by 12C/13C or H/D isotopic substitution renders the forbidden transition weakly allowed. The excitonic coupling (Davydov splitting) can then be measured between the S0 → S1 and S0 → S2 vibrationless bands. We discuss the mass-specific excitonic spectra of five H-bonded dimers that are supersonically cooled to a few K and investigated using two-color resonant two-photon ionization spectroscopy. The excitonic splittings Δcalc predicted by ab initio methods are 5–25 times larger than the experimental excitonic splittings Δexp. The purely electronic ab initio splittings need to be reduced (“quenched”), reflecting the coupling of the electronic transition to the optically active vibrations of the monomers. The so-called quenching factors Γ < 1 can be determined from experiment (Γexp) and/or calculation (Γcalc). The vibronically quenched splittings Γ·Δcalc are found to nicely reproduce the experimental exciton splittings.

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.