Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines

• Autorzy: Furmańczyk H. , Kubale M.

Identyfikatory

DOI

10.1515/bpasts-2017-0004

• Języki publikacji: EN

Abstrakty

EN

In the paper we consider the problem of scheduling n identical jobs on 4 uniform machines with speeds s1 ≥ s2 ≥ s3 ≥ s4, respectively. Our aim is to find a schedule with a minimum possible length. We assume that jobs are subject to some kind of mutual exclusion constraints modeled by a bipartite incompatibility graph of degree Δ, where two incompatible jobs cannot be processed on the same machine. We show that the general problem is NP-hard even if s1 = s2 = s3. If, however, Δ ≤ 4 and s1 ≥ 12s2, s2 = s3 = s4, then the problem can be solved to optimality in time O(n1.5). The same algorithm returns a solution of value at most 2 times optimal provided that s1 ≥ 2s2. Finally, we study the case s1 ≥ s2 ≥ s3 = s4 and give a 32/15-approximation algorithm running also in O(n1.5) time.

Słowa kluczowe

EN

equitable coloring; NP-hardness; polynomial algorithm; scheduling; uniform machine

PL

kolorowanie grafów; twardość NP; algorytm wielomianowy; planowanie

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2017
• Tom: Vol. 65, nr 1
• Strony: 29--34
• Opis fizyczny: Bibliogr. 12 poz., rys., tab., wykr.

Twórcy

autor

Furmańczyk H.

• Institute of Informatics, University of Gdańsk, Wita Stwosza 57, 80-309 Gdańsk, Poland

autor

Kubale M.

• Institute of Informatics, University of Gdańsk, Wita Stwosza 57, 80-309 Gdańsk, Poland

Bibliografia

• [1] M. Boudhar, “Scheduling a batch processing machine with bipartite compatibility graphs”, Math. Methods Oper. Res. 57, 513-527 (2003).
• [2] M. Boudhar, “Scheduling on a batch processing machine with split compatibility graphs”, J. Math. Modell. Algorithms 4, 391- 407 (2005).
• [3] G. Finke, V. Jost, M. Queyranne, A. Sebó, “Batch processing with interval graph compatibilities between tasks”, Disc. Appl. Math. 156, 556-568 (2008).
• [4] M. Demange, D. de Werra, J. Monnot, V.Th. Paschos, “Time slot scheduling of compatible jobs”, J. Scheduling 10, 111-127 (2007).
• [5] D. de Werra, M. Demange, J. Monnot, V.Th. Paschos, “A hypocoloring model for batch scheduling”, Disc. Appl. Math. 146, 3-26 (2005).
• [6] H. Furmańczyk, M. Kubale, “Scheduling of unit-length jobs with cubic Incompatibility graphs on three uniform machines”, Disc. Appl. Math., in print, available online 22 Feb. 2016.
• [7] S.-S. Li, Y.-Z. Zhang, “Serial batch scheduling on uniform parallel machines to minimize total completion time”, Inf. Process. Lett. 114, 692-695 (2014).
• [8] B.-L. Chen, C.-H. Yen, “Equitable Δ-coloring of graphs”, Disc. Math. 312, 1512-1517 (2012).
• [9] J.E. Hopcroft, R.M. Karp, “An n5/2 algorithm for maximum matchings in bipartite graphs”, SIAM J. Comput. 2, 225-231 (1973).
• [10] H.L. Bodlaender, K. Jansen, “On the complexity of scheduling incompatible jobs with unit-times”, LNCS 711, 291-300 (1993).
• [11] D. König, “Gráfok és mátrixok”, Matematikai és Fizikai Lapok 38, 116-119 (1931), [in Hungarian].
• [12] M. Kubale, “Interval vertex-coloring of a graph with forbidden colors”, Disc. Math. 74, 125-136 (1989).

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).