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

Yumei Huo (CUNY) | November 1 | Sublinear Space and Sublinear Time Algorithms for the Scheduling Problems.
by Zdeněk Hanzálek 30 Oct '23

30 Oct '23

Dear scheduling researcher, We are delighted to announce the talk given by Yumei Huo (CUNY). The title is " Sublinear Space and Sublinear Time Algorithms for the Scheduling Problems ". The seminar will take place on Zoom on Wednesday, November 1 at 14:00 UTC. Please check carefully the summer/winter time change in your country. Join Zoom Meeting https://cesnet.zoom.us/j/98815907109?pwd=QlUvQWV2a0k1M2ZKMEN1cW8xanN4dz09 Meeting ID: 988 1590 7109 Passcode: 224328 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Our research focuses on algorithmic big data solutions for scheduling problems, with a goal of devising efficient algorithm design principles in two key areas: sub-linear space algorithms and sub-linear time algorithms. The sub-linear space algorithm design aims to develop streaming algorithms that can approximate the optimal solution in just a few passes (often just one) over the data, utilizing limited space. On the other hand, the sub-linear time algorithm design strives to develop sampling algorithms that can approximate the optimal solution using a small portion of the input data and operate within sub-linear time. The next talk in our series will be: Claire Hanen (Sorbonne U., LIP6) | November 15 | Fixed Parameter Tractability of scheduling dependent typed tasks with time windows. 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

Dirk Briskorn (Uni of Wuppertal) | October 18 | Single-machine scheduling with an external resource
by Zdeněk Hanzálek 16 Oct '23

16 Oct '23

Dear scheduling researcher, We are delighted to announce the talk given by Dirk Briskorn (Uni of Wuppertal). The title is "Single-machine scheduling with an external resource". The seminar will take place on Zoom on Wednesday, October 18 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/96860317751?pwd=OHZBVlpHMlp4clNSTU4wNmRVL2VkZz09 Meeting ID: 968 6031 7751 Passcode: 635870 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 a single-machine scheduling problem with an external resource, which is rented for a non-interrupted period. Jobs that need this external resource are executed only when the external resource is available. There is a cost associated with the scheduling of jobs and a cost associated with the duration of the renting period of the external resource. We look at four classes of problems with an external resource: a class of problems where the renting period is budgeted and the scheduling cost needs to be minimized, a class of problems where the scheduling cost is budgeted and the renting period needs to be minimized, a class of two-objective problems where both, the renting period and the scheduling cost, are to be minimized, and a class of problems where a linear combination of the scheduling cost and the renting period is minimized. We provide a thorough complexity analysis (NP-hardness proofs and (pseudo-)polynomial algorithms) for different members of these four classes. The next talk in our series will be: Yumei Huo (CUNY) | November 1 | Sublinear Space and Sublinear Time Algorithms for the Scheduling Problems. 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

Kan Fang (Tianjin University) | October 4 | Single machine scheduling in additive manufacturing with two-dimensional packing constraints
by Zdeněk Hanzálek 02 Oct '23

02 Oct '23

Dear scheduling researcher, We are delighted to announce the talk given by Kan Fang (Tianjin University). The title is "Single machine scheduling in additive manufacturing with two-dimensional packing constraints". The seminar will take place on Zoom on Wednesday, October 4 at 13:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/97361696066?pwd=Z2hBcFFNZzArQWFPd3YyR1cwUzZIQT09 Meeting ID: 973 6169 6066 Passcode: 950886 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. In this talk, we focus on a single machine scheduling in additive manufacturing, in which parts can be produced simultaneously in a batch with two-dimensional packing constraints, and the objective is to minimize the makespan. In order to solve this problem, we propose an approximation algorithm with constant approximation ratio, and develop a combinatorial Benders decomposition based exact algorithm with various Benders cuts and acceleration strategies. We also conduct extensive computational experiments to test the performance of our proposed solution approaches. The next talk in our series will be: Dirk Briskorn (Uni of Wuppertal) | October 18 | Single-machine scheduling with an external resource. 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