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.

A hybrid method for large-scale short-term scheduling of make-and-pack production processes

Due to the ongoing trend towards increased product variety, fast-moving consumer goods such as food and beverages, pharmaceuticals, and chemicals are typically manufactured through so-called make-and-pack processes. These processes consist of a make stage, a pack stage, and intermediate storage facilities that decouple these two stages. In operations scheduling, complex technological constraints must be considered, e.g., non-identical parallel processing units, sequence-dependent changeovers, batch splitting, no-wait restrictions, material transfer times, minimum storage times, and finite storage capacity. The short-term scheduling problem is to compute a production schedule such that a given demand for products is fulfilled, all technological constraints are met, and the production makespan is minimised. A production schedule typically comprises 500–1500 operations. Due to the problem size and complexity of the technological constraints, the performance of known mixed-integer linear programming (MILP) formulations and heuristic approaches is often insufficient. We present a hybrid method consisting of three phases. First, the set of operations is divided into several subsets. Second, these subsets are iteratively scheduled using a generic and flexible MILP formulation. Third, a novel critical path-based improvement procedure is applied to the resulting schedule. We develop several strategies for the integration of the MILP model into this heuristic framework. Using these strategies, high-quality feasible solutions to large-scale instances can be obtained within reasonable CPU times using standard optimisation software. We have applied the proposed hybrid method to a set of industrial problem instances and found that the method outperforms state-of-the-art methods.

A continuous-time MILP model for short-term scheduling of make-and-pack production processes

In process industries, make-and-pack production is used to produce food and beverages, chemicals, and metal products, among others. This type of production process allows the fabrication of a wide range of products in relatively small amounts using the same equipment. In this article, we consider a real-world production process (cf. Honkomp et al. 2000. The curse of reality – why process scheduling optimization problems are diffcult in practice. Computers & Chemical Engineering, 24, 323–328.) comprising sequence-dependent changeover times, multipurpose storage units with limited capacities, quarantine times, batch splitting, partial equipment connectivity, and transfer times. The planning problem consists of computing a production schedule such that a given demand of packed products is fulfilled, all technological constraints are satisfied, and the production makespan is minimised. None of the models in the literature covers all of the technological constraints that occur in such make-and-pack production processes. To close this gap, we develop an efficient mixed-integer linear programming model that is based on a continuous time domain and general-precedence variables. We propose novel types of symmetry-breaking constraints and a preprocessing procedure to improve the model performance. In an experimental analysis, we show that small- and moderate-sized instances can be solved to optimality within short CPU times.

Scheduling in service systems: an application in the event-tourism industry

This paper deals with an event-bus tour booked by Bollywood film fans. During the tour, the participants visit selected locations of famous Bollywood films at various sites in Switzerland. Moreover, the tour includes stops for lunch and shopping. Each day, up to five buses operate the tour; for organizational reasons, two or more buses cannot stay at the same location simultaneously. The planning problem is how to compute a feasible schedule for each bus such that the total waiting time (primary objective) and the total travel time (secondary objective) are minimized. We formulate this problem as a mixed-integer linear program, and we report on computational results obtained with the Gurobi solver.

Optimal Scheduling of Work-Content-Constrained Projects

The execution of a project requires resources that are generally scarce. Classical approaches to resource allocation assume that the usage of these resources by an individual project activity is constant during the execution of that activity; in practice, however, the project manager may vary resource usage 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 various work-content-related constraints are met. We formulate this problem for the first time as a mixed-integer linear program. Our computational results for a standard test set from the literature indicate that this model outperforms the state-of-the-art solution methods for this problem.

Decision Support Models for Composing and Navigating through e-Learning Objects

Libraries of learning objects may serve as basis for deriving course offerings that are customized to the needs of different learning communities or even individuals. Several ways of organizing this course composition process are discussed. Course composition needs a clear understanding of the dependencies between the learning objects. Therefore we discuss the metadata for object relationships proposed in different standardization projects and especially those suggested in the Dublin Core Metadata Initiative. Based on these metadata we construct adjacency matrices and graphs. We show how Gozinto-type computations can be used to determine direct and indirect prerequisites for certain learning objects. The metadata may also be used to define integer programming models which can be applied to support the instructor in formulating his specifications for selecting objects or which allow a computer agent to automatically select learning objects. Such decision models could also be helpful for a learner navigating through a library of learning objects. We also sketch a graph-based procedure for manual or automatic sequencing of the learning objects.

Phase diagram with an enhanced spin-glass region of the mixed Ising–XY magnet LiHo{x}Er{1-x}F{4}

We present the experimental phase diagram of LiHoxEr1-xF4, a dilution series of dipolar-coupled model magnets. The phase diagram was determined using a combination of ac susceptibility and neutron scattering. Three unique phases in addition to the Ising ferromagnet LiHoF4 and the XY antiferromagnet LiErF4 have been identified. Below x = 0.86, an embedded spin-glass phase is observed, where a spin glass exists within the ferromagnetic structure. Below x = 0.57, an Ising spin glass is observed consisting of frozen needlelike clusters. For x ∼ 0.3–0.1, an antiferromagnetically coupled spin glass occurs. A reduction of TC(x) for the ferromagnet is observed which disobeys the mean-field predictions that worked for LiHoxY1-xF4.

Index Tracking Using Data-Mining Techniques and Mixed-Binary Linear Programming

Index tracking has become one of the most common strategies in asset management. The index-tracking problem consists of constructing a portfolio that replicates the future performance of an index by including only a subset of the index constituents in the portfolio. Finding the most representative subset is challenging when the number of stocks in the index is large. We introduce a new three-stage approach that at first identifies promising subsets by employing data-mining techniques, then determines the stock weights in the subsets using mixed-binary linear programming, and finally evaluates the subsets based on cross validation. The best subset is returned as the tracking portfolio. Our approach outperforms state-of-the-art methods in terms of out-of-sample performance and running times.

Ventilation-perfusion ratio in perflubron during partial liquid ventilation

BACKGROUND: Functional magnetic resonance imaging (fMRI) of fluorine-19 allows for the mapping of oxygen partial pressure within perfluorocarbons in the alveolar space (Pao(2)). Theoretically, fMRI-detected Pao(2) can be combined with the Fick principle approach, i.e., a mass balance of oxygen uptake by ventilation and delivery by perfusion, to quantify the ventilation-perfusion ratio (Va/Q) of a lung region: The mixed venous blood and the inspiratory oxygen fraction, which are equal for all lung regions, are measured. In addition, the local expiratory oxygen fraction and the end capillary oxygen content, both of which may differ between the lung regions, are calculated using the fMRI-detected Pao(2). We investigated this approach by numerical simulations and applied it to quantify local Va/Q in the perfluorocarbons during partial liquid ventilation. METHODS: Numerical simulations were performed to analyze the sensitivity of the Va/Q calculation and to compare this approach with another one proposed by Rizi et al. in 2004 (Magn Reson Med 2004;52:65-72). Experimentally, the method was used during partial liquid ventilation in 7 anesthetized pigs. The Pao(2) distribution in intraalveolar perflubron was measured by fluorine-19 MRI. Respiratory gas fractions together with arterial and mixed venous blood samples were taken to quantify oxygen partial pressure and content. Using the Fick principle, the local Va/Q was estimated. The impact of gravity (nondependent versus dependent) of perflubron dose (10 vs 20 mL/kg body weight) and of inspired oxygen fraction (Fio(2)) (0.4-1.0) on Va/Q was examined. RESULTS: In numerical simulations, the Fick principle proved to be appropriate over the Va/Q range from 0.02 to 2.5. Va/Q values were in acceptable agreement with the method published by Rizi et al. In the experimental setting, low mean Va/Q values were found in perflubron (confidence interval [CI] 0.08-0.29 with 20 mL/kg perflubron). At this dose, Va/Q in the nondependent lung was higher (CI 0.18-0.39) than in the dependent lung regions (CI 0.06-0.16; P = 0.006; Student t test). Differences depending on Fio(2) or perflubron dose were, however, small. CONCLUSION: The results show that derivation of Va/Q from local Po(2) measurements using fMRI in perflubron is feasible. The low detected Va/Q suggests that oxygen transport into the perflubron-filled alveolar space is significantly restrained.