Minimizing makespan with release times on identical parallel batching machines

2005 
We consider the problem of scheduling n jobs on m identical parallel batching machines. Each job is characterized by a release time and a processing time. Each machine can process up to B (B < n) jobs as a batch simultaneously. The processing time of a batch is equal to the largest processing time among all jobs in the batch. The objective is to minimize the maximum completion time (makespan). We present a polynomial time approximation scheme (PTAS) for this problem.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    10
    References
    38
    Citations
    NaN
    KQI
    []