September 2021 - Scheduling seminar - list.iid.ciirc.cvut.cz

Leah Epstein (University of Haifa) | September 29 | The benefit of preemption
by Zdeněk Hanzálek 22 Sep '21

22 Sep '21

Dear scheduling researcher, We are delighted to announce the talk given by Leah Epstein (University of Haifa). The title is "The benefit of preemption". The seminar will take place on Zoom on Wednesday, September 29 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/97989356749?pwd=T2NzMkszN2Y1RDNNZExTc3p0SjJDdz09 <https://cesnet.zoom.us/j/97989356749?pwd=T2NzMkszN2Y1RDNNZExTc3p0SjJDdz09> Meeting ID: 979 8935 6749 Passcode: 307940 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Given an input of a scheduling problem, any non-preemptive solution for it can be used as a preemptive solution. Thus, the optimal cost of a preemptive solution is not larger than that of an optimal non-preemptive solution. As preemption comes at a cost in real-life applications, it is of interest to find the worst-case ratio between the two costs. For a given problem, the supremum ratio over all possible inputs of the ratio between the two costs (of an optimal solution without preemption and an optimal solution that possibly uses preemption) is called the power or benefit of preemption. While many scheduling variants can be studied with respect to this measure, we will focus on the cases of a single machine, parallel identical machines, and uniformly related machines, and we will discuss the objectives of makespan and total (weighted) completion time. We will exhibit how one can benefit from preemption, and we will analyze the resulting worst case ratios for several basic models. The next talk in our series will be given by Federico Della Croce (DIGEP - Polito.it) | October 13 | The Longest Processing Time Rule for Identical Parallel Machines Revisited. 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

Nicholas G. Hall (The Ohio State Uni) | September 15 | Dynamic Opponent Choice in Tournaments
by Zdeněk Hanzálek 13 Sep '21

13 Sep '21

Dear scheduling researcher, We are delighted to announce the talk given by Nicholas G. Hall (The Ohio State University). The title is "Dynamic Opponent Choice in Tournaments". The seminar will take place on Zoom on Wednesday, September 15 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/99180641475?pwd=WkpNS1NkVXNCcnVzdURqSzU1YXM3QT09 <https://cesnet.zoom.us/j/99180641475?pwd=WkpNS1NkVXNCcnVzdURqSzU1YXM3QT09> Meeting ID: 991 8064 1475 Passcode: 994980 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. We propose an alternative design for tournaments that use a preliminary stage, followed by several rounds of single elimination play. Most U.S. major sports, for example, are organized in this way. However, the conventional "bracket" design of these tournaments suffers from several deficiencies. First, top ranked players randomly incur unfortunate matchups against other players, which introduces an unnecessary element of luck. Second, as documented in the tournament design literature, various reasonable criteria such as stronger ranked players having a higher probability of winning, are not satisfied. Third, the probability that the top two players meet is not maximized. Fourth, there is the widely observed issue of shirking at the preliminary stage, where a player loses deliberately to obtain an easier path through the tournament. Finally, the use of a conventional fixed bracket fails to allow players to consider information that develops during the tournament, such as injuries to other players. To address all these issues, we allow higher ranked players at the single elimination stage to choose their next opponent at each round. We allow each player's ranking either to remain static, or to improve from beating a higher ranked player. Using data from 1,902 men's professional tennis tournaments from 2001-2016, we demonstrate the reasonableness of the results obtained. We also perform sensitivity analysis for the effect of increasing irregularity in the pairwise win probability matrix on three traditional performance measures. Finally, we show that our opponent choice design reduces shirking, and could have eliminated it in some notorious situations. In summary, compared with the conventional design, the opponent choice design provides higher probabilities that the best player wins and also that the two best players meet, reduces shirking, and performs well for preservation of ranking. The next talk in our series will be given by Leah Epstein (University of Haifa) | September 29 | The benefit of preemption. 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

Nicholas G. Hall (The Ohio State Uni) | September 15 | Dynamic Opponent Choice in Tournaments
by Zdeněk Hanzálek 01 Sep '21

01 Sep '21

Dear scheduling researcher, We are delighted to announce the talk given by Nicholas G. Hall (The Ohio State University). The title is "Dynamic Opponent Choice in Tournaments". The seminar will take place on Zoom on Wednesday, September 15 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/99180641475?pwd=WkpNS1NkVXNCcnVzdURqSzU1YXM3QT09 <https://cesnet.zoom.us/j/99180641475?pwd=WkpNS1NkVXNCcnVzdURqSzU1YXM3QT09> Meeting ID: 991 8064 1475 Passcode: 994980 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. We propose an alternative design for tournaments that use a preliminary stage, followed by several rounds of single elimination play. Most U.S. major sports, for example, are organized in this way. However, the conventional "bracket" design of these tournaments suffers from several deficiencies. First, top ranked players randomly incur unfortunate matchups against other players, which introduces an unnecessary element of luck. Second, as documented in the tournament design literature, various reasonable criteria such as stronger ranked players having a higher probability of winning, are not satisfied. Third, the probability that the top two players meet is not maximized. Fourth, there is the widely observed issue of shirking at the preliminary stage, where a player loses deliberately to obtain an easier path through the tournament. Finally, the use of a conventional fixed bracket fails to allow players to consider information that develops during the tournament, such as injuries to other players. To address all these issues, we allow higher ranked players at the single elimination stage to choose their next opponent at each round. We allow each player's ranking either to remain static, or to improve from beating a higher ranked player. Using data from 1,902 men's professional tennis tournaments from 2001-2016, we demonstrate the reasonableness of the results obtained. We also perform sensitivity analysis for the effect of increasing irregularity in the pairwise win probability matrix on three traditional performance measures. Finally, we show that our opponent choice design reduces shirking, and could have eliminated it in some notorious situations. In summary, compared with the conventional design, the opponent choice design provides higher probabilities that the best player wins and also that the two best players meet, reduces shirking, and performs well for preservation of ranking. The next talk in our series will be given by Leah Epstein (University of Haifa) | September 29 | The benefit of preemption. 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