×

The coupled unit-time operations problem on identical parallel machines with respect to the makespan. (English) Zbl 1408.90137

Summary: This paper addresses the problem of scheduling \(n\) unit-time coupled operations on \(m\) identical parallel machines with minimum time delay considerations so as to minimize the overall completion time, known as the makespan. Two approximation algorithms, along with their worst-case analysis, are presented.

MSC:

90B35 Deterministic scheduling theory in operations research
68W25 Approximation algorithms
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahr, D.; Bekesi, J.; Galambos, G.; Oswald, M.; Reinelt, G., An exact algorithm for scheduling identical coupled tasks, Math. Methods Oper. Res., 59, 93-203, (2004) · Zbl 1138.90390
[2] Baptiste, Ph., A note on scheduling identical coupled tasks in logarithmic time, J. Discrete Appl. Math., 158, 583-587, (2010) · Zbl 1196.90046
[3] Blazewicz, J.; Ecker, E.; Kis, K.; Potts, C. N.; Tanas, M.; Whitehead, J. D., Scheduling of coupled tasks with unit processing times, J. Sched., 13, 453-461, (2010) · Zbl 1208.68090
[4] Brauner, N.; Finke, G.; Lehoux-Lebacque, V.; Potts, C. N.; Whitehead, J. D., Scheduling of coupled tasks and one-machine no-wait robotic cells, Comput. Oper. Res., 36, 301-307, (2009) · Zbl 1157.90406
[5] Brucker, P.; Knust, S., Complexity results for single-machine problems with positive finish start-time-lags, Computing, 63, 299-316, (1999) · Zbl 0946.90026
[6] J.N.D. Gupta, Single facility scheduling with two operations per job and time-lags, Preprint, 1994.
[7] Orman, A. J.; Potts, C. N.; Shahani, A. K.; Moore, A. R., Scheduling for a multifunction phased array radar system, European J. Oper. Res., 90, 13-25, (1996) · Zbl 0916.90153
[8] Potts, C. N.; Whitehead, J. D., Heuristics for a coupled-operation problem, J. Oper. Res. Soc., 58, 1375-1388, (2007) · Zbl 1177.90179
[9] Shapiro, R. D., Scheduling coupled tasks, Nav. Res. Logist. Q., 27, 477-481, (1980)
[10] Simonin, G.; Giroudeau, R.; Konig, J. C., Polynomial time algorithms for scheduling problems for coupled-tasks in the presence of treatment tasks, Electron. Notes Discrete Math., 36, 647-654, (2010) · Zbl 1237.90098
[11] Yu, W.; Hoogeveen, H.; Lenstra, J. K., Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard, J. Sched., 7, 333-348, (2004) · Zbl 1154.90506
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.