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


FB3 Cutting and Packing
June 11, 2021  10:45 AM
3 - TC Koopmans

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.