Scheduling seminar

Download

schedulingseminar@rtime.felk.cvut.cz

January 2024

1 participants
1 discussions

Klaus Heeger (Ben Gurion University) | January 24 | Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
by Zdeněk Hanzálek 22 Jan '24

22 Jan '24

Dear scheduling researcher, We are delighted to announce the talk given by Klaus Heeger (Ben Gurion University). The title is " Minimizing the Weighted Number of Tardy Jobs is W[1]-hard ". The seminar will take place on Zoom on Wednesday, January 24 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/92404235122?pwd=cFVxSVBPS28wS3dhYVQ5WVhJcEVkUT09 Meeting ID: 924 0423 5122 Passcode: 536766 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. We consider the 1 || ∑ wj Uj problem, the problem of minimizing the weighted number of tardy jobs on a single machine. This problem is one of the most basic and fundamental problems in scheduling theory, with several different applications both in theory and practice. We prove that 1 || ∑ wj Uj is W[1]-hard with respect to the number of different processing times in the input, as well as with respect to the number of different weights in the input. This, along with previous work, provides a complete picture for 1 || ∑ wj Uj from the perspective of parameterized complexity, as well as almost tight complexity bounds for the problem under the Exponential Time Hypothesis (ETH). Based on joint work with Danny Hermelin. The next talk in our series will be: Ceyda Oğuz (Koç University) | February 7 | A Matheuristic for the Generalized Order Acceptance and Scheduling Problem. For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- 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