Campus Event Calendar
Event Entry
New for: D1, D2, D3, D4
What and Who
Stability radius of an optimal schedule
Prof. DSC. Yuri N. Sotskov
Inst. of Engineering Cybernetics of the Academy of Sciences, Belarus
Talk
AG 1, AG 2, AG 3, AG 4
Expert Audience
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 22 January 2001
11:00
-- Not specified --
15
101
Saarbrücken
Abstract
We investigate the two-machine n-job flow-shop scheduling problem with
the objective of minimizing the makespan and given non-availability
intervals on each of the two machines. It was proven recently that this
problem is NP-hard even if there is only one non-availability interval
either on the first machine or on the second machine. If there are no
non-availability intervals on any machine, then the two-machine flow-shop
problem may be solved using Johnson's schedule constructed in O(n log n)
time. Our results demonstrate that the optimality of Johnson's schedule
is not violated if there exist only sufficiently small non-availability
intervals. The instrument we use is stability analysis which answers the
question how stable the property of a schedule to be optimal is if there
are independent changes in the processing times of the jobs.
Contact
Dipl.-Inform. Oliver Braun
302-4336
--email hidden
passcode not visible
logged in users only