Minimizing mean completion time in a batch processing system (Q1879250)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Minimizing mean completion time in a batch processing system
scientific article

    Statements

    Minimizing mean completion time in a batch processing system (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    22 September 2004
    0 references
    We consider batch processing jobs to minimize the mean completion time. A batch processing machine can handle up to \(B\) jobs simultaneously. Each job is represented by an arrival time and a processing time. Jobs processed in a batch have the same completion time, i.e., their common starting time plus the processing time of their longest job. For batch processing, non-preemptive scheduling is usually required and we discuss this case. The batch processing problem reduces to the ordinary uniprocessor system scheduling problem if \(B=1\). We focus on the other extreme case \(B=+\infty\). Even for this seemingly simple extreme case, we are able to show that the problem is NP-hard for the weighted version. In addition, we establish a polynomial time algorithm for a special case when there are only a constant number of job processing times. Finally, we give a polynomial time approximation scheme for the general case.
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references