Open block scheduling in optical communication networks.

*(English)*Zbl 1097.68011Summary: In this paper the process of data transmission in star coupled optical communication networks is modelled as a shop-type scheduling problem, where channels (wavelengths) are treated as machines. We formulate an Open Block problem with the minimum makespan objective \((OB||C_{\max})\) in which a relation of a new type between the operations of each job is introduced: any two operations of a job have identical processing times and may be processed either simultaneously (in a common block) or, alternatively, at disjoint time intervals. We show that the problem is polynomially solvable for 4 machines, NP-hard for 6 machines and strongly NP-hard for a variable number of machines. For the case of a variable number of machines we present a polynomial time \(\sqrt 2\)-approximation algorithm and prove that there is no polynomial time \(\rho\)-approximation algorithm with \(\rho < 11/10\), unless \(\text{P}=\text{NP}\). For the case when the number of machines is fixed, we show that the problem admits a linear time PTAS. In addition, we show that the two-machine problem with release dates is NP-hard in the strong sense.

##### MSC:

68M10 | Network design and communication in computer systems |

68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |

PDF
BibTeX
XML
Cite

\textit{A. A. Ageev} et al., Theor. Comput. Sci. 361, No. 2--3, 257--274 (2006; Zbl 1097.68011)

Full Text:
DOI

##### References:

[1] | A.K. Amoura, E. Bampis, C. Kenyon, Y. Manoussakis, Scheduling independent multiprocessor tasks, in: Proc. Fifth European Symp. on Algorithms (1997), Lecture Notes in Computer Science, Vol. 1284, Springer, Berlin, 1997, pp. 1-12. · Zbl 0990.68023 |

[2] | I. Baldine, L. Jackson, G. Rouskas, Helios: a broadcast optical architecture, in: Proc. Second Internat. IFIP-TC6 Networking Conf. (Piza, Italy, 2002), Lecture Notes in Computer Science, Vol. 2345, Springer, Berlin, 2002, pp. 887-898. · Zbl 1046.68668 |

[3] | E. Bampis, M. Caramia, J. Fiala, A.V. Fishkin, A. Iovanella, On scheduling of independent dedicated multiprocessor tasks, in: Proc. 13th Internat. Symp. on Algorithms and Computation, Vancouver, BC, Canada, 2002, Lecture Notes in Computer Science, Vol. 2518, Springer, Berlin, 2002, pp. 391-402. · Zbl 1019.68008 |

[4] | Brucker, P., Scheduling algorithms, (1995), Springer Berlin, Heidelberg, New York · Zbl 0839.90059 |

[5] | Fiala, T., An algorithm for the open-shop problem, Math. oper. res., 8, 100-109, (1983) · Zbl 0506.90037 |

[6] | A.V. Fishkin, K. Jansen, L. Porkolab, On minimizing average weighted completion time of multiprocessor tasks with release dates, in: Proc. 28th Internat. Colloq. on Automata, Languages and Programming (Crete, 2001), Lecture Notes in Computer Science, Vol. 2076, Springer, Berlin, 2001, pp. 875-886. · Zbl 0986.68007 |

[7] | O. Gerstel, B. Li, A. McGuire, G.N. Rouskas, K. Sivalingam, Z. Zhang (Eds.), Special issue on protocols and architectures for next generations optical wdm networks, IEEE J. Selected Areas in Commun. 18 (2000). |

[8] | Gonzalez, T.; Sahni, S., Open shop scheduling to minimize finish time, J. ACM, 23, 665-679, (1976) · Zbl 0343.68031 |

[9] | Hoogeveen, J.A.; de Velde, S.L.V.; Veltman, B., Complexity of scheduling multiprocessor tasks with prespecified processor allocations, Discrete appl. math., 55, 259-272, (1994) · Zbl 0938.68671 |

[10] | Kuznetsov, M.; Froberg, N.; Henion, S.; Rao, H.; Korn, J.; Rauschenbach, K.; Modiano, E.; Chan, V., A next-generation optical regional access networks, IEEE commun. mag., 38, 66-72, (2000) |

[11] | B. Mukherjee, WDM-based local lightwave networks part I: single-hop systems, IEEE Network Mag. (1992), 12-27. |

[12] | Rouskas, G.N., Scheduling algorithms for unicast, multicast, and broadcast, (), 171-188 |

[13] | Sevast’janov, S.V., Polynomially solvable case of the open-shop problem with arbitrary number of machines, Cybernet. systems anal., 28, 918-933, (1992), (Translated from Russian) · Zbl 0875.90320 |

[14] | Sevast’janov, S.V., Vector summation in Banach space and polynomial algorithms for flow shops and open shops, Math. oper. res., 20, 90-103, (1995) · Zbl 0834.90074 |

[15] | Sevastianov, S., Nonstrict vector summation in multi-operation scheduling, Ann. oper. res., 83, 179-211, (1998) · Zbl 0913.90181 |

[16] | Sevastianov, S.V.; Woeginger, G.J., Makespan minimization in open shops: a polynomial time approximation scheme, Math. programming, 82, 191-198, (1998) · Zbl 0920.90075 |

[17] | Sevastianov, S.V.; Woeginger, G.J., Linear time approximation scheme for the multiprocessor open shop problem, Discrete appl. math., 114, 273-288, (2001) · Zbl 1020.68016 |

[18] | D. Thaker, G.N. Rouskas, Multi-destination communication in broadcast WDM networks: a survey, Technical Report 2000-08, North Caroline State University, 2000. |

[19] | The NGI Helious project: Regional Testbed Optical Access Network For IP Multicast and Differentiated Services. \(\langle\)http://projects.anr.mcnc.org/Helios/⟩, 2000. |

[20] | Wagner, R.E.; Alferness, R.C.; Saleh, A.A.M.; Goodman, M.S., J. lightwave technol., 14, 1349, (1996) |

[21] | Williamson, D.P.; Hall, L.A.; Hoogeveen, J.A.; Hurkens, C.A.J.; Lenstra, J.K.; Sevastianov, S.V.; Shmoys, D.B., Short shop schedules, Oper. res., 45, 288-294, (1997) · Zbl 0890.90112 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.