The complexity of shop-scheduling problems with two or three jobs (Q1178530)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The complexity of shop-scheduling problems with two or three jobs
scientific article

    Statements

    The complexity of shop-scheduling problems with two or three jobs (English)
    0 references
    26 June 1992
    0 references
    The author discusses job-shop, flow-shop and open-shop scheduling problems with two or three jobs. The performance criteria considered are the makespan, \(C_{max}\), mean flowtime and general regular criteria. Up to now, most of the scheduling models restrict the number of machines, but not the number of jobs. In this article the opposite approach is analyzed. The number of jobs is restricted to two or three and the number of machines may vary, but there are always more machines than jobs included. The results of the article are as follows. NP-hardness is proved for \(3| 5| J| C_{max}\) and \(3| 5| J, Pr| c_{max}\), both problems are job-shop problems with 3 jobs and 5 machines and the makespan as performance criterion, in the first problem job preemption is forbidden, whereas in the second problem jobs may be splitted. Next, NP-hardness is proved for \(3| m| F| C_{max}\), here a flow-job system with 3 jobs and an arbitrary number of machines is considered. Then NP-hardness is proved for \(3| 5| J|\sum C_ i\) and \(3| m| F|\sum C_ i\), both problems include the mean flowtime as performance criterion. Finally, some problems with only two jobs and a general regular performance measure, \(\Phi\), are discussed. Polynomial algorithms are developed for \(2| m| J|\Phi\), \(2| m| J\), \(Pr|\Phi\), \(2| m| F|\Phi\) and \(2| m| F\), \(Pr|\Phi\). These four problems can be transformed into a problem of finding shortest paths in special directed graphs.
    0 references
    0 references
    regular performance measures
    0 references
    job-shop
    0 references
    flow-shop
    0 references
    open-shop
    0 references
    makespan
    0 references
    mean flowtime
    0 references
    NP-hardness
    0 references
    Polynomial algorithms
    0 references
    directed graphs
    0 references
    0 references
    0 references