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


  • Szymon Duraj Gdańsk University of Technology
  • Paweł Kopeć Gdańsk University of Technology
  • Marek Kubale Gdańsk University of Technology
  • Tytus Pikies Gdańsk University of Technology



batch scheduling, bipartite graph, polynomial algorithm, uniform machines


Abstract. In the paper we consider the problem of scheduling of unit-length jobs on 3 or 4 uniform parallel machines to minimize schedule length or total completion time. We assume that jobs are subject to some kind of mutual exclusion constraints, modeled by a bipartite graph of bounded degree. The edges of the graph correspond to pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard, we show that under some conditions imposed on machine speeds and the structure of  incompatibility graph our problem can be solved to optimality in polynomial time. Theoretical considerations are accompanied by computer experiments  with some particular model of scheduling.


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.




How to Cite

Duraj, S., Kopeć, P., Kubale, M., & Pikies, T. (2017). Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines. Computational Experiments. Decision Making in Manufacturing and Services, 11(1-2), 53–61.