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/
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
