A new heuristic for open shop total completion time problem. (English) Zbl 1185.90096
Summary: The \(m\)-machine open shop problem to minimize the sum of the completion times is investigated in our paper. First, a heuristic algorithm, Shortest Processing Time Block, is presented to deal with problem \(O_m|n=km|\sum C_j\), where \(k\) is positive integer. And then, the heuristic is extended to solve the general problem \(O_m\|\sum C_j\). It is proved that the heuristic is asymptotically optimal when the job number goes to infinity. At the end of this paper, numerical experimentation results show the effectiveness of the heuristic algorithm.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Pinedo, M., Scheduling: Theory, Algorithms and Systems (2002), Prentice-Hall: Prentice-Hall New Jersey · Zbl 1145.90394 |
| [2] | Brucker, P., Scheduling Algorithms (2004), Springer-Verlag: Springer-Verlag Berlin · Zbl 1060.90034 |
| [3] | Achugbue, J. O.; Chin, F. Y., Scheduling the open shop to minimize mean flow time, SIAM J. Comput., 11, 709-720 (1982) · Zbl 0492.68038 |
| [4] | Brucker, P.; Jurisch, B.; Jurisch, M., Open shop problems with unit time operations, Math. Meth. Oper. Res., 37, 59-73 (1993) · Zbl 0776.90033 |
| [5] | Lann, A.; Mosheiov, G.; Rinott, Y., Asymptotic optimality in probability of a heuristic schedule for open shop with job overlaps, Oper. Res. Lett., 22, 63-68 (1998) · Zbl 0911.90213 |
| [6] | Liaw, C-F.; Cheng, C-Y.; Chen, M., The total completion time open shop scheduling problem with a given sequence of jobs on one machine, Comput. Oper. Res., 29, 1251-1266 (2002) · Zbl 0994.90062 |
| [7] | Bräsel, H.; Herms, A.; Mörig, M.; Tautenhahn, T.; Tusch, J.; Werner, F., Heuristic constructive algorithms for open shop scheduling to minimize mean flow time, Eur. J. Oper. Res., 189, 856-870 (2008) · Zbl 1146.90406 |
| [8] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic machine sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
