Single machine flow-time scheduling with a single breakdown (Q1111018)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Single machine flow-time scheduling with a single breakdown
scientific article

    Statements

    Single machine flow-time scheduling with a single breakdown (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    1989
    0 references
    We consider the problem of scheduling tasks on a single machine to minimize the flowtime. The machine is subject to breakdowns during the processing of the tasks. The breakdowns occur at random times and the machine is unavailable until it is repaired. The times for repair are random and independent of each other and of the breakdown process. A task that is preempted due to a breakdown must be restarted and otherwise preemptions are not allowed. We show in the case of a single breakdown that if the distribution function of the time to breakdown is concave then shortest processing time (SPT) first scheduling stochastically minimizes the flowtime. For the case of multiple breakdowns we show that SPT minimizes the expected flowtime when the times to breakdown are exponentially distributed. If the time for a single breakdown is known before scheduling begins, and the processing times of the tasks are also known, then we show that the problem of deciding whether there is a schedule with flowtime less than or equal to a given value is NP-complete. Finally, we bound the performance of SPT scheduling in the deterministic case when there is a single breakdown.
    0 references
    0 references
    flowtime minimization
    0 references
    scheduling
    0 references
    breakdowns
    0 references
    NP-complete
    0 references