On the general solution for a class of early/tardy problems (Q1207204)

From MaRDI portal
Revision as of 23:32, 14 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
On the general solution for a class of early/tardy problems
scientific article

    Statements

    On the general solution for a class of early/tardy problems (English)
    0 references
    0 references
    0 references
    0 references
    1 April 1993
    0 references
    The non-preemptive scheduling of \(n\) jobs with a common due date \(d\) on a single machine is considered. The objective is to find a schedule that minimizes \(\sum^ n_{j=1} | C_ j- d|^ r\), where \(C_ j\) is the completion time of job \(j\) and \(r\) is a positive integer. By generalizing known results for \(r=1\) and \(r=2\), various structural properties of an optimal solution are derived. These structural properties are used to derive a pseudopolynomial dynamic programming algorithm. Prior to applying this algorithm, it is assumed that the processing times and the due date are suitably scaled using an integer scaling factor so that optimal completion times of jobs are integers.
    0 references
    0 references
    non-preemptive scheduling
    0 references
    common due date
    0 references
    single machine
    0 references
    pseudopolynomial dynamic programming
    0 references

    Identifiers