The large-scale requirements of modern tooth manufacturing call for automated scheduling methods that can optimize multiple cost objectives while accounting for complex constraints. Previously, the artificial teeth scheduling problem (ATP) was formally introduced, along with exact and heuristic methods to approach challenging real-life scenarios. Although existing approaches provide feasible solutions for all practical benchmarks evaluated, optimal results remain unknown. We propose a novel solver-independent constraint modeling approach that solves the ATP through an innovative two-stage process. The first stage uses a subproblem formulation that batches product demands into compact jobs via constraint programming or column generation. In the second phase, the job sequence is optimized using a single-machine model with interval variables and global scheduling constraints. Experimental results with state-of-the-art constraint solvers and a heuristic demonstrate the approach’s effectiveness, yielding improved solutions across the majority of realistically sized benchmark instances.

We introduce the Oven Scheduling Problem (OSP), a new parallel batch scheduling problem that arises in the area of electronic component manufacturing. Jobs need to be scheduled to one of several ovens and may be processed simultaneously in one batch if they have compatible requirements. The scheduling of jobs must respect several constraints concerning eligibility and availability of ovens, release dates of jobs, setup times between batches as well as oven capacities. Running the ovens is highly energy-intensive and thus the main objective, besides finishing jobs on time, is to minimize the cumulative batch processing time across all ovens. This objective distinguishes the OSP from other batch processing problems which typically minimize objectives related to makespan, tardiness or lateness. We propose to solve this NP-hard scheduling problem via constraint programming (CP) and integer linear programming (ILP) and present corresponding CP- and ILP-models. For an experimental evaluation, we introduce a multi-parameter random instance generator to provide a diverse set of problem instances. Using state-of-the-art solvers, we evaluate the quality and compare the performance of our CP- and ILP-models, which could find optimal solutions for many instances. Furthermore, using our models we are able to provide upper bounds for the whole benchmark set including large-scale instances.

Finding efficient production schedules for automotive paint shops is a challenging task and several paint shop problem variants have been investigated in the past. In this work we focus on a recently introduced real-life paint shop scheduling problem appearing in the automotive supply industry where car parts, which need to be painted, are placed upon carrier devices. These carriers are placed on a conveyor belt and moved into painting cabins, where robots apply the paint. The aim is to find an optimized production schedule for the painting of car parts.

Factories in the automotive supply industry paint a large number of items requested by car manufacturing companies on a daily basis. As these factories face numerous constraints and optimization objectives, finding a good schedule becomes a challenging task in practice, and full-time employees are expected to manually create feasible production plans. In this study, we propose novel constraint programming models for a real-life paint shop scheduling problem. We evaluate and compare our models experimentally by performing a series of benchmark experiments using real-life instances in the industry. We also show that the decision variant of the paint shop scheduling problem is NP-complete.

The computation of string similarity measures has been thoroughly studied in the scientific literature and has applications in a wide variety of different areas. One of the most widely used measures is the so called string edit distance which captures the number of required edit operations to transform a string into another given string. Although polynomial time algorithms are known for calculating the edit distance between two strings, there also exist NP-hard problems from practical applications like scheduling or computational biology that constrain the minimum edit distance between arrays of decision variables. In this work, we propose a novel global constraint to formulate restrictions on the minimum edit distance for such problems. Furthermore, we describe a propagation algorithm and investigate an explanation strategy for an edit distance constraint propagator that can be incorporated into state of the art lazy clause generation solvers. Experimental results show that the proposed propagator is able to significantly improve the performance of existing exact methods regarding solution quality and computation speed for benchmark problems from the literature.

The present work exemplifies how parameter identifiability analysis can be used to gain insights into differences in experimental systems and how uncertainty in parameter estimates can be handled. The case study, presented here, investigates interferon-gamma (IFNγ) induced STAT1 signalling in two cell types that play a key role in pancreatic cancer development: pancreatic stellate and cancer cells. IFNγ inhibits the growth for both types of cells and may be prototypic of agents that simultaneously hit cancer and stroma cells. We combined time-course experiments with mathematical modelling to focus on the common situation in which variations between profiles of experimental time series, from different cell types, are observed. To understand how biochemical reactions are causing the observed variations, we performed a parameter identifiability analysis. We successfully identified reactions that differ in pancreatic stellate cells and cancer cells, by comparing confidence intervals of parameter value estimates and the variability of model trajectories. Our analysis shows that useful information can also be obtained from nonidentifiable parameters. For the prediction of potential therapeutic targets we studied the consequences of uncertainty in the values of identifiable and nonidentifiable parameters. Interestingly, the sensitivity of model variables is robust against parameter variations and against differences between IFNγ induced STAT1 signalling in pancreatic stellate and cancer cells. This provides the basis for a prediction of therapeutic targets that are valid for both cell types.