Name
Title | ||
|---|---|---|
Asymptotic optimality in probability of a heuristic schedule for open shops with job overlaps |
Abstract | ||
|---|---|---|
The assumption that different operations of a given job cannot be processed simultaneously is accepted in most classical multi-operation scheduling models. There are, however, real-life applications where parallel processing (within a given job) is possible. In this paper we study open shops with job overlaps, i.e., scheduling systems in which each job requires processing operations by M different machines, and different operations of a single job may be processed in parallel. The problem of computing an optimal schedule, that is, ordering the jobs' operations for each machine with the objective of minimizing the sum of job completion times, is NP-hard. A simple heuristic, based on ordering the jobs by the average processing time of the M operations required for each job, and a lower bound on the optimal cost are introduced. The lower bound is used to prove asymptotic optimality (in probability) of the heuristic when the processing times are i.i.d. from any distribution with a finite variance. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1016/S0167-6377(98)00007-8 | Oper. Res. Lett. |
Keywords | Field | DocType |
different operation,single job,heuristic schedule,m different machine,job overlap,job completion time,processing time,m operation,classical multi-operation scheduling model,asymptotic optimality,scheduling,open shop,parallel machines,parallel processing,convergence in probability,average processing time,lower bound | Open shop,Convergence of random variables,Mathematical optimization,Heuristic,Job shop scheduling,Upper and lower bounds,Scheduling (computing),Optimal cost,Job queue,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 2-3 | Operations Research Letters |
Citations | PageRank | References |
1 | 0.43 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Avital Lann | 1 | 31 | 3.78 |
| Gur Mosheiov | 2 | 1073 | 105.02 |
| Yosef Rinott | 3 | 22 | 5.48 |