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 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.

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.

MQN-Mapplet: Visualization of Chemical Space with Interactive Maps of DrugBank, ChEMBL, PubChem, GDB-11, and GDB-13

The MQN-mapplet is a Java application giving access to the structure of small molecules in large databases via color-coded maps of their chemical space. These maps are projections from a 42-dimensional property space defined by 42 integer value descriptors called molecular quantum numbers (MQN), which count different categories of atoms, bonds, polar groups, and topological features and categorize molecules by size, rigidity, and polarity. Despite its simplicity, MQN-space is relevant to biological activities. The MQN-mapplet allows localization of any molecule on the color-coded images, visualization of the molecules, and identification of analogs as neighbors on the MQN-map or in the original 42-dimensional MQN-space. No query molecule is necessary to start the exploration, which may be particularly attractive for nonchemists. To our knowledge, this type of interactive exploration tool is unprecedented for very large databases such as PubChem and GDB-13 (almost one billion molecules). The application is freely available for download at www.gdb.unibe.ch.

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.

Daytime Low Stratiform Cloud Detection on AVHRR Imagery

The near-real time retrieval of low stratiform cloud (LSC) coverage is of vital interest for such disciplines as meteorology, transport safety, economy and air quality. Within this scope, a novel methodology is proposed which provides the LSC occurrence probability estimates for a satellite scene. The algorithm is suited for the 1 × 1 km Advanced Very High Resolution Radiometer (AVHRR) data and was trained and validated against collocated SYNOP observations. Utilisation of these two combined data sources requires a formulation of constraints in order to discriminate cases where the LSC is overlaid by higher clouds. The LSC classification process is based on six features which are first converted to the integer form by step functions and combined by means of bitwise operations. Consequently, a set of values reflecting a unique combination of those features is derived which is further employed to extract the LSC occurrence probability estimates from the precomputed look-up vectors (LUV). Although the validation analyses confirmed good performance of the algorithm, some inevitable misclassification with other optically thick clouds were reported. Moreover, the comparison against Polar Platform System (PPS) cloud-type product revealed superior classification accuracy. From the temporal perspective, the acquired results reported a presence of diurnal and annual LSC probability cycles over Europe.

A novel clinical scoring system for outcome prediction in dogs with acute kidney injury managed by hemodialysis.

BACKGROUND No reliable tool to predict outcome of acute kidney injury (AKI) exists. HYPOTHESIS A statistically derived scoring system can accurately predict outcome in dogs with AKI managed with hemodialysis. ANIMALS One hundred and eighty-two client-owned dogs with AKI. METHODS Logistic regression analyses were performed initially on clinical variables available on the 1st day of hospitalization for relevance to outcome. Variables with P< or = .1 were considered for further analyses. Continuous variables outside the reference range were divided into quartiles to yield quartile-specific odds ratios (ORs) for survival. Models were developed by incorporating weighting factors assigned to each quartile based on the OR, using either the integer value of the OR (Model A) or the exact OR (Models B or C, when the etiology was known). A predictive score for each model was calculated for each dog by summing all weighting factors. In Model D, actual values for continuous variables were used in a logistic regression model. Receiver-operating curve analyses were performed to assess sensitivities, specificities, and optimal cutoff points for all models. RESULTS Higher scores were associated with decreased probability of survival (P < .001). Models A, B, C, and D correctly classified outcomes in 81, 83, 87, and 76% of cases, respectively, and optimal sensitivities/specificities were 77/85, 81/85, 83/90 and 92/61%, respectively. CONCLUSIONS AND CLINICAL RELEVANCE The models allowed outcome prediction that corresponded with actual outcome in our cohort. However, each model should be validated further in independent cohorts. The models may also be useful to assess AKI severity.

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.

The triplite–triploidite supergroup: structural modulation in wagnerite, discreditation of magniotriplite, and the new mineral hydroxylwagnerite

Electron-microprobe analysis, single-crystal X-ray diffraction with an area detector, and high-resolution transmission electron microscopy show that minerals related to wagnerite, triplite and triploidite, which are monoclinic Mg, Fe and Mn phosphates with the formula Me2+ 2PO4(F,OH), constitute a modulated series based on the average triplite structure. Modulation occurs along b and may be commensurate with (2b periodicity) or incommensurate but generally close to integer values (∼3b, ∼5b, ∼7b, ∼9b), i.e. close to polytypic behaviour. As a result, the Mg- and F-dominant minerals magniotriplite and wagnerite can no longer be considered polymorphs of Mg2PO4F, i.e., there is no basis for recognizing them as distinct species. Given that wagnerite has priority (1821 vs. 1951), the name magniotriplite should be discarded in favour of wagnerite. Hydroxylwagnerite, end-member Mg2PO4OH, occurs in pyrope megablasts along with talc, clinochlore, kyanite, rutile and secondary apatite in two samples from lenses of pyrope–kyanite–phengite–quartz-schist within metagranite in the coesite-bearing ultrahigh-pressure metamorphic unit of the Dora-Maira Massif, western Alps, Vallone di Gilba, Val Varaita, Piemonte, Italy. Electron microprobe analyses of holotype hydroxylwagnerite and of the crystal with the lowest F content gave in wt%: P2O5 44.14, 43.99; SiO2 0.28, 0.02; SO3 –, 0.01; TiO2 0.20, 0.16; Al2O3 0.06, 0.03; MgO 48.82, 49.12; FeO 0.33, 0.48; MnO 0.01, 0.02; CaO 0.12, 0.10; Na2O 0.01, –; F 5.58, 4.67; H2O (calc) 2.94, 3.36; –O = F 2.35, 1.97; Sum 100.14, 99.98, corresponding to (Mg1.954Fe0.007Ca0.003Ti0.004Al0.002Na0.001)Σ=1.971(P1.003Si0.008)Σ=1.011O4(OH0.526F0.474)Σ=1 and (Mg1.971Fe0.011Ca0.003Ti0.003Al0.001)Σ=1.989(P1.002Si0.001)Σ=1.003O4(OH0.603F0.397)Σ=1, respectively. Due to the paucity of material, H2O could not be measured, so OH was calculated from the deficit in F assuming stoichiometry, i.e., by assuming F + OH = 1 per formula unit. Holotype hydroxylwagnerite is optically biaxial (+), α 1.584(1), β 1.586(1), γ 1.587(1) (589 nm); 2V Z(meas.) = 43(2)°; orientation Y = b. Single-crystal X-ray diffraction gives monoclinic symmetry, space group P21/c, a = 9.646(3) Å, b = 12.7314(16) Å, c = 11.980(4) Å, β = 108.38(4) , V = 1396.2(8) Å3, Z = 16, i.e., hydroxylwagnerite is the OH-dominant analogue of wagnerite [β-Mg2PO4(OH)] and a high-pressure polymorph of althausite, holtedahlite, and α- and ε-Mg2PO4(OH). We suggest that the group of minerals related to wagnerite, triplite and triploidite constitutes a triplite–triploidite super-group that can be divided into F-dominant phosphates (triplite group), OH-dominant phosphates (triploidite group), O-dominant phosphates (staněkite group) and an OH-dominant arsenate (sarkinite). The distinction among the three groups and a potential fourth group is based only on chemical features, i.e., occupancy of anion or cation sites. The structures of these minerals are all based on the average triplite structure, with a modulation controlled by the ratio of Mg, Fe2+, Fe3+ and Mn2+ ionic radii to (O,OH,F) ionic radii.