Author name cluster

Felix Winter

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

ICAPS Conference 2021 Conference Paper

Automated Production Scheduling for Artificial Teeth Manufacturing

Felix Winter
Christoph Mrkvicka
Nysret Musliu
Jakob Preininger

In industrial artificial teeth manufacturing, nowadays a high level of automation is utilized to produce a large quantity of teeth in short production cycles. As a large variety of different product shapes and colors have to be processed on a single machine, the creation of efficient production schedules becomes a very challenging task. Due to the complexity of the problem and several cost minimization objectives that need to be considered, there usually is a large potential to improve the currently manually created schedules with automated solution methods. In this paper, we formally specify and solve a novel challenging real-life machine batch scheduling problem from the area of artificial teeth manufacturing. Additionally, we provide a collection of real-life benchmark instances that can be used to evaluate solution methods for the problem. To efficiently solve the problem, we propose an innovative construction heuristic and metaheuristic approach as well as an exact method using constraint programming. An extensive experimental evaluation shows that exact techniques can efficiently solve small scheduling scenarios and can provide optimal solutions for four instances. Furthermore, we show that the proposed metaheuristic approach is able to reach optimal results for small instances and can find high quality solutions also for large real-life benchmark instances.

Details

TIST Journal 2021 Journal Article

Constraint-based Scheduling for Paint Shops in the Automotive Supply Industry

Felix Winter
Nysret Musliu

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.

Details DOI

AAAI Conference 2020 Conference Paper

Explaining Propagators for String Edit Distance Constraints

Felix Winter
Nysret Musliu
Peter Stuckey

The computation of string similarity measures has been thoroughly studied in the scientiﬁc 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.

PDF Details

ICAPS Conference 2019 Conference Paper

Solution Approaches for an Automotive Paint Shop Scheduling Problem

Felix Winter
Nysret Musliu
Emir Demirovic
Christoph Mrkvicka

In the paint shops of the automotive supply industry, a large number of synthetic material pieces need to be painted every day to provide the large variety of items required for car manufacturing. Because of the sophisticated automated production process and the tight due dates requested by car manufacturers, finding an optimized production schedule becomes a challenging task that is at the present time performed by multiple human planners. In this paper, we formulate and solve a novel real-life paint shop scheduling problem from the automotive supply industry which introduces unique constraints and objectives that do not appear in the existing literature. Additionally, we provide a new collection of benchmark instances based on real-life planning scenarios that can be used to evaluate solution techniques for the problem. An exact approach based on constraint programming is able to provide optimal solutions for smaller instances, but many larger instances could not be solved yet. Therefore, we propose a metaheuristic method based on local search that uses novel neighborhood relations and various ways to escape local optima. Our approach is able to provide feasible solutions for all instances within reasonable running time.

Details

IS Journal 2017 Journal Article

A Hybrid Approach for the Sudoku Problem: Using Constraint Programming in Iterated Local Search

Nysret Musliu
Felix Winter

Sudoku is not only a popular puzzle but also an interesting and challenging constraint satisfaction problem. Therefore, automatic solving methods have been the subject of several publications in the past two decades. Although current methods provide good solutions for small-sized puzzles, larger instances remain challenging. This article introduces a new local search technique based on the min-conflicts heuristic for Sudoku. Furthermore, the authors propose an innovative hybrid search technique that exploits constraint programming as a perturbation technique within the iterated local search framework. They experimentally evaluate their methods on challenging benchmarks for Sudoku and report improvements over state-of-the-art solutions. To show the generalizability of the proposed approach, they also applied their method on another challenging scheduling problem. The results show that the proposed method is also robust in another problem domain.

Details DOI