W. Skowrońska, S. Gawiejnowicz
Optimal schedules for some scheduling problems with fixed processing times have the property, called V-shape property, such that jobs are scheduled in non-increasing and non-decreasing order with respect to processing times before and after the job with the smallest processing time, respectively. There are also known scheduling problems with variable processing times, where the property is defined not with respect to processing times but with respect some other problem parameters, e.g. job deterioration rates. Sequences corresponding to such schedules are called V-shaped sequences and are studied in various contexts.
In the talk, first we summarize known properties of the V-shaped sequences. Next, we show how the sequences can be generated by a known non-recursive algorithm and a new recursive algorithm. Finally, we show how to apply the algorithms to solving of some scheduling problems with variable time-dependent job processing times. We illustrate our presentation with results of numerical experiments with implementations of discussed algorithms in Python 3.8.
Keywords: V-shaped sequences, algorithms, scheduling
Scheduled
FB3 Cutting and Packing
June 11, 2021 10:45 AM
3 - TC Koopmans
