Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines : Computational Experiments

• Autorzy: Szymon Duraj , Paweł Kopeć , Marek Kubale , Tytus Pikies
• Języki publikacji: EN

Abstrakty

EN

In this paper, we consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard, we show that our problem can be solved to optimality in polynomial time under some restrictions imposed on the number of machines, their speeds, and the structure of the incompatibility graph. The theoretical considerations are accompanied by computer experiments with a certain model of scheduling.(original abstract)

Słowa kluczowe

EN

Machinery and equipment; Task scheduler; Mathematic calculations; Scientific experiment

PL

Maszyny i urządzenia; Harmonogram zadań; Obliczenia matematyczne; Eksperyment badawczy

• Czasopismo: Decision Making in Manufacturing and Services
• Rocznik: 2017
• Tom: 11
• Numer: nr 1/2
• Strony: 53--61

Twórcy

autor

Szymon Duraj

• Gdańsk University of Technology

autor

Paweł Kopeć

• Gdańsk University of Technology

autor

Marek Kubale

• Gdańsk University of Technology

autor

Tytus Pikies

• Gdańsk University of Technology

Bibliografia

• Furmanczyk H., Kubale M., 2017a., Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines. Bulletin PAS - Tech. Sci., 65, pp. 29-34.
• Furmanczyk H., Kubale M., 2017b., Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines. Disc. Appl. Math., 00, pp. 00-00.
• Furmanczyk H., Kubale M., submitted., Sharp bounds for the complexity of semiequitable coloring of cubic and subcubic graphs.
• Kosowski A., 2009., A note on the strength and minimum color sum of bipartite graphs. Disc. Appl. Math., 157, pp. 2552-2554.
• Małafiejski M., Giaro K., Janczewski R., Kubale M., 2004., Sum coloring of bipartite graphs with bounded degree. Algorithmica, 40, pp. 235-244.
• Steger A., Wormald N. C., 1999., Generating random regular graphs quickly. Comb., Probab. and Comput., 8, pp. 377-396.

Identyfikatory

DOI

https://doi.org/10.7494/dmms.2017.11.1-2.53