Better polynomial algorithms for scheduling unit-length jobswith bipartite incompatibility graphs on uniform machines
The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-appr...
Main Authors: | T. Pikies, M. Kubale |
---|---|
Format: | Article |
Language: | English |
Published: |
Polish Academy of Sciences
2019-02-01
|
Series: | Bulletin of the Polish Academy of Sciences: Technical Sciences |
Subjects: | |
Online Access: | https://journals.pan.pl/Content/111100/PDF/03_031-036_00776_Bpast.No.67-1_06.02.20.pdf |
Similar Items
-
The complexity of cost constrained vehicle scheduling problem
by: Malihe Niksirat, et al.
Published: (2021-02-01) -
Scheduling equal-length jobs with arbitrary sizes on uniform parallel batch machines
by: Xin Xiao, et al.
Published: (2023-02-01) -
Greedy Firefly Algorithm for Optimizing Job Scheduling in IoT Grid Computing
by: Adil Yousif, et al.
Published: (2022-01-01) -
A Note on Polynomial Algorithm for Cost Coloring of Bipartite Graphs with Δ ≤ 4
by: Giaro Krzysztof, et al.
Published: (2020-08-01) -
Scheduling Algorithms in Fog Computing: A Survey
by: Khaled Matrouk, et al.
Published: (2021-01-01)