October 2025 - Scheduling seminar - list.iid.ciirc.cvut.cz

Zijie Zhou (IEDA, HKUST) | October 29 | Efficient and Robust Large Language Model (LLM) Inference Scheduling Optimization
by Zdenek Hanzalek 27 Oct '25

27 Oct '25

Dear scheduling researcher, We are delighted to announce the talk given by Zijie Zhou (IEDA, HKUST). The title is "Efficient and Robust Large Language Model (LLM) Inference Scheduling Optimization". The seminar will take place on Zoom on Wednesday, October 29 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91957974467?pwd=bIbyEXuAi693d5e0YLjaxmFFYZQOpF.1 Meeting ID: 919 5797 4467 Passcode: 291598 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. We study the problem of optimizing Large Language Model (LLM) inference scheduling to minimize total completion time. LLM inference is an online and multi-task service process and also heavily energy consuming by which a pre-trained LLM processes input requests and generates output tokens sequentially. Therefore, it is vital to improve its scheduling efficiency and reduce the power consumption while a great amount of prompt requests are arriving. There are two key challenges: (i) each request has heterogeneous prefill and decode lengths. In LLM serving, the prefill length corresponds to the input prompt length, which determines the initial memory usage in the KV cache. The decode length refers to the number of output tokens generated sequentially, with each additional token increasing the KV cache memory usage by one unit. We show that minimizing total completion time is NP-hard due to the interplay of batching, placement constraints, precedence relationships, and linearly increasing memory usage. We then analyze commonly used scheduling strategies in practice, such as First-Come-First-Serve (FCFS) and Shortest-First (SF), and prove that their competitive ratios are unbounded. To address this, we propose a novel algorithm based on a new selection metric that efficiently forms batches over time. We prove that this algorithm achieves a constant competitive ratio. (ii) the output length, which critically impacts memory usage and processing time, is unknown. We first design a conservative algorithm, Amax, which schedules requests based on the upper bound of predicted output lengths to prevent memory overflow. However, this approach is overly conservative: as prediction accuracy decreases, performance degrades significantly due to potential overestimation. To overcome this limitation, we propose Amin, an adaptive algorithm that initially treats the predicted lower bound as the output length and dynamically refines this estimate during inferencing. We prove that Amin achieves a log-scale competitive ratio. The next talk in our series will be: Rachel R. Chen (UC Davis) | November 12 | Outpatient Appointment Scheduling with Waiting Time Limits For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek Hanzalek, Michael Pinedo and Guohua Wan -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0

Correction Changhyun Kwon (KAIST/Omelet, Inc.) | October 15 | Learning-Based Approaches to Combinatorial Optimization in Transportation
by Zdenek Hanzalek 13 Oct '25

13 Oct '25

Dear scheduling researcher, We are delighted to announce the talk given by Changhyun Kwon (KAIST/Omelet, Inc.). The title is " Learning-Based Approaches to Combinatorial Optimization in Transportation ". The seminar will take place on Zoom on Wednesday, October 15 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96320878964?pwd=0IzVyJYar5VdTRAJIYtRHU8qxkSNes.1 Meeting ID: 963 2087 8964 Passcode: 883125 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Combinatorial optimization problems arising in transportation are often NP-hard, making them computationally challenging to solve at scale. Recent advances in machine learning have opened new avenues for tackling such problems, either as standalone solution strategies or by enhancing traditional optimization algorithms. This talk surveys a spectrum of learning-based approaches for transportation optimization, including: (i) end-to-end learning models, (ii) integration within exact algorithms, (iii) learning to guide local search, (iv) accelerating metaheuristics, (v) embedding within optimization formulations, and (vi) test-time search strategies. This talk will discuss the principles behind each approach, highlight representative applications, and reflect on both their current potential and open challenges for the future of transportation optimization. The next talk in our series will be: Zijie Zhou (IEDA, HKUST) | October 29 | Efficient and Robust Large Language Model (LLM) Inference Scheduling Optimization For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek Hanzalek, Michael Pinedo and Guohua Wan -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0

Changhyun Kwon (KAIST/Omelet, Inc.) | October 1 | Learning-Based Approaches to Combinatorial Optimization in Transportation
by Zdenek Hanzalek 13 Oct '25

13 Oct '25

Dear scheduling researcher, We are delighted to announce the talk given by Changhyun Kwon (KAIST/Omelet, Inc.). The title is " Learning-Based Approaches to Combinatorial Optimization in Transportation ". The seminar will take place on Zoom on Wednesday, October 29 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96320878964?pwd=0IzVyJYar5VdTRAJIYtRHU8qxkSNes.1 Meeting ID: 963 2087 8964 Passcode: 883125 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Combinatorial optimization problems arising in transportation are often NP-hard, making them computationally challenging to solve at scale. Recent advances in machine learning have opened new avenues for tackling such problems, either as standalone solution strategies or by enhancing traditional optimization algorithms. This talk surveys a spectrum of learning-based approaches for transportation optimization, including: (i) end-to-end learning models, (ii) integration within exact algorithms, (iii) learning to guide local search, (iv) accelerating metaheuristics, (v) embedding within optimization formulations, and (vi) test-time search strategies. This talk will discuss the principles behind each approach, highlight representative applications, and reflect on both their current potential and open challenges for the future of transportation optimization. The next talk in our series will be: Zijie Zhou (IEDA, HKUST) | October 29 | Efficient and Robust Large Language Model (LLM) Inference Scheduling Optimization For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek Hanzalek, Michael Pinedo and Guohua Wan -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0