File ShortestJobFirst.h

↰ Parent directory (ADS/optimization)

Shortest Job First (exercise 14.5): n programs of durations t_i, run one after the other, in the order that minimizes the average time of completion: by increasing duration, since moving the shortest program to the front of any order does not increase any time of completion; O( n log n ).

Definition (ADS/optimization/ShortestJobFirst.h)

Detailed Description

With the weights w_i of the programs (the probabilities of the files on a tape, read at the times of completion), the order of least weighted sum :math:` sum_i w_i C_i ` of the times of completion C_i is Smith’s rule, by increasing :math:` t_i / w_i , compared as :math: t_a w_b < t_b w_a ` (no division, and a program of weight 0 goes last): the exchange of two adjacent programs a , b changes the sum by :math:` t_a w_b - t_b w_a `; O( n log n ). With precedence constraints the problem is NP-hard in general, and solved by Lawler’s merging of chains on series-parallel orders.

The contracts [see File Contract.h]: the times are not negative, the order is by increasing time, and the order given to totalCompletion() has places of t; the weights are not negative and no program has both time and weight 0, and the order of smithOrder() is by increasing t / w. The operations are defined in ShortestJobFirst.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, exercise 14.5, https://algoritmicamente.it/materiali/libro/capitoli/cap14.pdf

    1. Smith, Various optimizers for single-stage production, Naval Research Logistics Quarterly 3(1-2), 59-66, 1956, doi:10.1002/nav.3800030106

    1. Lawler, Sequencing jobs to minimize total weighted completion time subject to precedence constraints, Annals of Discrete Mathematics 2, 75-90, 1978, doi:10.1016/S0167-5060(08)70323-6

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions