Scheduling seminar November 2022

schedulingseminar@rtime.felk.cvut.cz

1 participants
2 discussions

Sigrid Knust (Uni of Osnabrück) | November 23 | Synchronous flow shop scheduling problems

by Zdeněk Hanzálek

Dear scheduling researcher, We are delighted to announce the talk given by Sigrid Knust (Uni of Osnabrück). The title is "Synchronous flow shop scheduling problems". The seminar will take place on Zoom on Wednesday, November 23 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/91616587714?pwd=SFJGcnpVbTFSSWFGVWt5WHFwL2xuQT09 Meeting ID: 916 1658 7714 Passcode: 332102 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. A synchronous flow shop is a variant of a non-preemptive permutation flow shop where transfers of jobs from one machine to the next take place at the same time. The processing is organized in synchronized cycles which means that in a cycle all current jobs start at the same time on the corresponding machines. Then all jobs are processed and have to wait until the last one is finished. Afterwards, all jobs are moved to the next machine simultaneously. As a consequence, the processing time of a cycle is determined by the maximum processing time of the operations contained in it. Furthermore, only permutation schedules are feasible, i.e., the jobs have to be processed in the same order on all machines. The goal is to find a permutation of the jobs such that the makespan is minimized. Motivated by a practical application in production planning at a company assembling shelf boards for kitchen elements, we investigate different aspects of synchronous flow shop problems. Especially, we consider the situation of dominating machines, additional resources, setup times and leaving machines idle. The next talk in our series will be in January 2023. 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/

6 months, 1 week

Alessandro Agnetis (University of Siena) | November 9 | Scheduling machines subject to unrecoverable failures and other related stochastic sequencing problems

by Zdeněk Hanzálek

Dear scheduling researcher, We are delighted to announce the talk given by Alessandro Agnetis (University of Siena). The title is " Scheduling machines subject to unrecoverable failures and other related stochastic sequencing problems ". The seminar will take place on Zoom on Wednesday, November 9 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/98121270904?pwd=aUxmUk5iNENoU3czUmo1Vzg1b3U2dz09 Meeting ID: 981 2127 0904 Passcode: 729055 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Typical scheduling problems deal with a set of activities (jobs) requiring various resources (machines) to be performed. In most scheduling scenarios, it is assumed that machines are continuously avalable (possibly except in some scheduled maintenance intervals), and this gives rise to problems in which the typical scheduling objectives (makespan, total weighted completion time etc) are pursued. A significantly different scenario arises if machines may actually fail, i.e., (i) while performing a job i, a machine becomes unavailable (e.g. breaks down) with probability \pi_i, and (ii) such failures are unrecoverable, in the sense that from then onwards the machine is lost and so are the jobs already allocated and not yet processed on that machine. If a job i is successfully completed, a reward r_i is attained. In this context, the basic problem is how to assign the jobs to the machines and how to sequence them so that the expected reward is maximized. In this talk we review the main results, discuss relationships with other sequencing problems and point out some open problems. We address the following scenarios. 1) m parallel (identical) machines. While the single-machine case is easy, for two or more machines the problem is hard and various approaches have been proposed to address it. For general m, list scheduling yields a 0.8531-approximate solution. The argument of the proof is similar to the one used by Schwiegelshohn to prove Kawaguchi and Kyan's bound for the minimization of total weighted completion time. 2) In order to hedge against machine failures, one can use job replication. In this case, copies of the same job can be scheduled on different machines, and the reward r_i is attained if at least one copy is successfully completed. Although also this problem is hard for m>=2, relatively simple algorithms provide solutions which are provably close to optimality. 3) This class of sequencing problems is also related to testing problems, as follows. A system consists of n components, each of which can be either functioning or not. Only if all components are functioning, the system is "up". Component i is functioning with probability \pi_i, and testing it costs c_i. As soon as a component that is not functioning is detected, the testing stops (concluding that the system is "down"). The problem is to decide in which order should the components be tested, in order to minimize the expected costs. While the single-tester problem is solved by a simple priority rule, various problem variants can be considered. In particular, if several testers operate in parallel, under time constraints, the problem gets more complicated. While it is NP-hard for three or more testers, its complexity with two testers is still open. The next talk in our series will be: Sigrid Knust (Uni of Osnabrück) | November 23 | Synchronous flow shop 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/

6 months, 3 weeks

2023

2022

2021