Helmut Sedding

About

I am a computer scientist and employed as a Senior Researcher at the Institute of Data Analysis and Process Design in the Operations Research & Operations Management group at ZHAW Zurich University of Applied Sciences in Switzerland. With generous support of the sponsors, I organize the event on AI-driven Decision Intelligence: Shaping Operations for Efficiency and Sustainability.

My scientific and professional career focuses on algorithms and methods for discrete optimization, particularly within scheduling, production planning, project planning and logistics. A specialty is the focus on dynamic variants where parameters change over time, see e.g., our International Workshop on Dynamic Scheduling Problems.

At Ulm University in Germany, I was awarded a Doctor (Dr. rer. nat.) summa cum laude and graduated with a Diplom (Dipl.-Inf.). Both theses were evaluated at the Institute of Theoretical Computer Science.

Previously, I was the lead developer for a novel 3d planning software, which became established to plan assembly lines of major automobile manufacturers and was honored as a “best product” of the LogiMAT international trade fair.

For object recognition, we devised one of the very first massively parallel compute pipelines on the GPU for calculating convolutions and extracting features in real-time.

Finally, let me welcome you to mail me at .

Publications

Journal papers

1. Sedding, H. A. (2024). Mixed-Model Moving Assembly Line Material Placement Optimization for a Shorter Time-Dependent Worker Walking Time.
   Journal of Scheduling, 27(3), 257–275.
   [PDF] [doi:10.1007/s10951-023-00787-5] [abstract
   Car mass production commonly involves a moving assembly line that mixes several car models. This requires plenty of material supplies at the line side, but available space is scarce. Thus, material is placed apart from ideal positions. Then, picking it up involves walking along the line. This time is non-productive and can encompass 10–15% of total production time. Thus, it is important to estimate and minimize it during production planning. However, the calculations are difficult because the conveyor continuously moves. Therefore, most literature bounds walking time by a constant, but this discards valuable potential. To better approximate it, we use a time-dependent V-shaped function. A comparison indicates that for a majority of instances, constant walking time estimates of 95% confidence are at least 51% higher. Then, we introduce a model to optimize material positions such that the model-mix walking time is minimized. This poses an NP-hard sequencing problem with a recursive and nonlinear objective function. Our key discovery is a lower bound on the objective of partial solutions, established by a Lagrangian relaxation that can be solved in quadratic time. Resulting branch and bound based algorithms allow to quickly and reliably optimize up to the largest real world sized instances.
   ]
2. Sedding, H. A. (2020). Scheduling Jobs with a V-shaped Time-Dependent Processing Time.
   Journal of Scheduling, 23(6), 751–768.
   [PDF] [doi:10.1007/s10951-020-00665-4] [abstract
   In the field of time-dependent scheduling, a job’s processing time is specified by a function of its start time. While monotonic processing time functions are well-known in the literature, this paper introduces non-monotonic functions with a convex, piecewise-linear V-shape similar to the absolute value function. They are minimum at an ideal start time, which is the same for all given jobs. Then, the processing time equals the job’s basic processing time. Earlier or later, it increases linearly with slopes that can be asymmetric and job-specific. The objective is to sequence the given jobs on a single machine and minimize the makespan. This is motivated by production planning of moving car assembly lines, in particular, to sequence a worker’s assembly operations such that the time-dependent walking times to gather materials from the line-side are minimized. This paper characterizes the problem’s computational complexity in several angles. NP-hardness is observed even if the two slopes are the same for all jobs. A fully polynomial time approximation scheme is devised for the more generic case of agreeable ratios of basic processing time and slopes. In the most generic case with job-specific slopes, several polynomial cases are identified.
   ]
3. Sedding, H. A. (2020). Line Side Placement for Shorter Assembly Line Worker Paths.
   IISE Transactions, 52(2), 181–198.
   Best Paper Award in Scheduling and Logistics.
   [PDF] [doi:10.1080/24725854.2018.1508929] [abstract
   Placing material containers at moving assembly lines is an intriguing problem because each container position influences worker paths. This optimization is relevant in practice as worker walking time accounts for about 10–15% of total work time. Nonetheless, we find few computational approaches in the literature. We address this gap and model walking time to containers, then optimize their placement. Our findings suggest this reduces walking time of intuitive solutions by an average of 20%, with considerable estimated savings. To investigate the subject, we formulate a quintessential optimization model for basic sequential container placement along the line side. However, even this core problem turns out as strongly NP-complete. Nonetheless, it possesses several polynomial cases that allow to construct a lower bound on the walking time. Moreover, we discover exact and heuristic dominance conditions between partial placements. This facilitates an exact and a truncated branch-and-bound solution algorithm. In extensive tests, they consistently deliver superior performance compared to several mixed integer programming and metaheuristic approaches. To aid practitioners in quickly recognizing instances with high optimization potential even before performing a full optimization, we provide a criterion to estimate it with just few measurements.
   ]
4. Jaehn, F., Sedding, H. A. (2016). Scheduling with Time-Dependent Discrepancy Times.
   Journal of Scheduling, 19(6), 737–757.
   [PDF] [doi:10.1007/s10951-016-0472-2] [abstract
   In time-dependent scheduling, various processing time functions are studied, yet absolute value functions have surprisingly been omitted from the discussion. Such a processing time function increases linearly with a job’s discrepancy from its ideal midtime. The objective is to find a schedule that minimizes the makespan, introducing the discrepancy time minimization problem. This single-machine scheduling problem with time-dependent processing times is motivated by optimization of walking times on a car assembly line. Its decision version is NP hard, as we show by reduction of the even–odd partition problem. For the variant with known start time, we develop several heuristics. Further insights form lower bounds and dominance rules for a branch-and-bound search. Numerical experiments show the performance of our algorithms on problem instances of up to 60 jobs. For the variant with common ideal midtime and flexible start time, we present a polynomial-time algorithm.
   ]

Books

1. Sedding, H. A. (2020).
   Time-Dependent Path Scheduling: Algorithmic Minimization of Walking Time at the Moving Assembly Line.
   Springer Vieweg.
   [doi:10.1007/978-3-658-28415-2] [abstract
   Moving assembly lines are the stepping stone for mass production of automobiles. Here, every second counts, which necessitates planners to meticulously optimize them. A crucial factor is each worker’s nonproductive walking time between the moving workpiece and line-side material containers for picking up required material. Minimizing the walking time is difficult because the workpiece moves steadily. Helmut A. Sedding devises algorithms to optimize the sequence of work operations, and the placement of material containers. Thereby, he introduces a novel category of time-dependent scheduling problems, and lays the basis for the algorithmic optimization of time-dependent paths at the moving assembly line.
   ]

Conference and workshop papers

1. Halman, N., Sedding, H. A. (2024). A Faster FPTAS for Makespan Minimization with Time-Dependent Agreeable V-shaped Processing Times.
   Proceedings of the 19th International Workshop on Project Management and Scheduling, 57–60.
   
2. Sedding, H., Seidel, M. (2023). Lot Sizing and Scheduling of Injection Molding Machines with Setup Resources and Demand Uncertainty.
   Proceedings of the 4th International Workshop on Dynamic Scheduling Problems, 95–100.
   [doi:10.14708/isbn.978-83-962157-1-0p95-100]
3. Sedding, H. A., Seidel, M. (2023). Lot Sizing and Scheduling of Injection Molding Machines with Setup Resources and Demand Uncertainty.
   Proceedings of the 4th International Workshop on Dynamic Scheduling Problems.
   
4. Sedding, H. A. (2021). A Lower Bound for Sequentially Placing Boxes at the Moving Assembly Line to Minimize Walking Time.
   Proceedings of the 3rd International Workshop on Dynamic Scheduling Problems, 63–69.
   
5. Sedding, H. A. (2021). An FPTAS for Scheduling with Piecewise-Linear Nonmonotonic Convex Time-Dependent Processing Times and Job-Specific Agreeable Slopes.
   Proceedings of the 17th International Workshop on Project Management and Scheduling.
   
6. Sedding, H. A. (2019). Scheduling with Asymmetric Piecewise-Linear Time-Dependent Processing Times.
   Proceedings of the 14th Workshop on Models and Algorithms for Planning and Scheduling Problems, 43–45.
   
7. Sedding, H. A. (2018). Scheduling Non-Monotonous Convex Piecewise-Linear Time-Dependent Processing Times.
   Proceedings of the 2nd International Workshop on Dynamic Scheduling Problems, 79–84.
   
8. Sedding, H. A. (2018). On the Complexity of Scheduling Start Time Dependent Asymmetric Convex Processing Times.
   Proceedings of the 16th International Conference on Project Management and Scheduling, 209–212.
   
9. Sedding, H. A. (2017). Box Placement as Time Dependent Scheduling to Reduce Automotive Assembly Line Worker Walk Times.
   Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems, 92–94.
   
10. Sedding, H. A. (2017). Scheduling of Time-Dependent Asymmetric Nonmonotonic Processing Times Permits an FPTAS.
    Proceedings of the 15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 135–138.
    
11. Sedding, H. A., Jaehn, F. (2014). Single Machine Scheduling with Nonmonotonic Piecewise Linear Time Dependent Processing Times.
    Proceedings of the 14th International Conference on Project Management and Scheduling, 222–225.
    
12. Sedding, H., Deger, F., Dammertz, H., Bouecke, J., Lensch, H. (2010). Massively Parallel Multiclass Object Recognition.
    Proceedings of the 15th Vision, Modeling and Visualization Workshop, 251–257.
    [PDF] [doi:10.2312/PE/VMV/VMV10/251-257] [abstract
    We present a massively parallel object recognition system based on a cortex-like structure. Due to its nature, this general, biologically motivated system can be parallelized efficiently on recent many-core graphics processing units (GPU). By implementing the entire pipeline on the GPU, by rigorously optimizing memory bandwidth and by minimizing branch divergence, we achieve significant speedup compared to both recent CPU as well as GPU implementations for reasonably sized feature dictionaries. We demonstrate an interactive application even on a less powerful laptop which is able to classify webcam images and to learn novel categories in real time.
    ]

Technical journal articles

1. Herrmann, T., Sedding, H. (2019). Industrie 4.0 von morgen diskutiert.
   Technische Rundschau, 111(10), 74–75.
   [abstract
   Die Digitalisierung der Produktion stellt Unternehmer, Mitarbeiter, Lieferanten und IT-Spezialisten vor mannigfaltige Herausforderungen. Gemeinsames Element ist dabei die Planung und Steuerung der Produktionsprozesse. In Winterthur haben sich am 4.9.2019 rund einhundert Vertreter aus Unternehmen, Verbänden und Hochschulen zur jährlichen Konferenz „Perspektiven mit Industrie 4.0“ getroffen.
   ]
2. Sedding, H. (2019). Das digitale Produktions-Puzzle.
   Technische Rundschau, 111(7), 54–55.
   [abstract
   Ein wichtiger Schritt für die industrielle Massenproduktion war die Einführung der Fliessbandmontage im Automobilbau, denn sie erlaubt ein effektives Ineinandergreifen aller Elemente. Seither hat sich diese Produktionswelt stetig weiterentwickelt hin zu digitalisierten und algorithmisch optimierten Produktionsstrassen. Helmut Sedding, Wissenschaftler an der ZHAW School of Engineering am Institut für Datenanalyse und Prozessdesign, nennt in geraffter Form die wesentlichen Mechanismen.
   ]

Talks

1. Sedding, H. (2022).
   Scheduling with Time-Dependent Processing Time Functions of V-shaped Linear Pieces.
   18th Swiss Operations Research Days.
   [abstract
   Scheduling is classically centered around jobs with constant processing times. This allows for universal methods of a simple structure, like Smith’s rule, proven by job interchange arguments. Certain applications, however, entail variable processing times, depending on the job’s start time. Then, interchanging jobs implies changing start times for successive jobs, which escalates the computational complexity. To plan car assembly on a moving conveyor line, we are concerned with time-dependent processing time functions that are V-shaped and piecewise-linear. We present complexity results and draw relations to classic scheduling problems.
   ]
2. Sedding, H. (2021).
   Line Side Placement for Shorter Assembly Line Worker Paths.
   IISE Annual Virtual Conference & Expo 2021: IISE Transactions (Journal) Best Paper Award in Scheduling and Logistics.
   [abstract
   Placing material containers at moving assembly lines is an intriguing problem because each container position influences worker paths. This optimization is relevant in practice as worker walking time accounts for about 10–15% of total work time. Nonetheless, we find few computational approaches in the literature. We address this gap and model walking time to containers, then optimize their placement. Our findings suggest this reduces walking time of intuitive solutions by an average of 20%, with considerable estimated savings. To investigate the subject, we formulate a quintessential optimization model for basic sequential container placement along the line side. However, even this core problem turns out as strongly NP-complete. Nonetheless, it possesses several polynomial cases that allow to construct a lower bound on the walking time. Moreover, we discover exact and heuristic dominance conditions between partial placements. This facilitates an exact and a truncated branch-and-bound solution algorithm. In extensive tests, they consistently deliver superior performance compared to several mixed integer programming and metaheuristic approaches. To aid practitioners in quickly recognizing instances with high optimization potential even before performing a full optimization, we provide a criterion to estimate it with just few measurements.
   ]