Approximation Algorithms for Two-machine Flow-shop Scheduling with a Conflict Graph
Full Text: Cai2018_Chapter_ApproximationAlgorithmsForTwo-.pdf
Path cover is a well-known intractable problem whose goal is to find a minimum number of vertex disjoint paths in a given graph to cover all the vertices. We show that a variant, where the objective function is not the number of paths but the number of length-0 paths (that is, isolated vertices), turns out to be polynomial-time solvable. We further show that another variant, where the objective function is the total number of length-0 and length-1 paths, is also polynomial-time solvable. Both variants find applications in approximating the two-machine flow-shop scheduling problem in which job processing constraints are formulated as a conflict graph. For the unit jobs, we present a 4/3-approximation algorithm for the scheduling problem with an arbitrary conflict graph, based on the exact algorithm for the variants of the path cover problem. For arbitrary jobs where the conflict graph is the union of two disjoint cliques (i.e., all the jobs can be partitioned into two groups such that the jobs in a group are pairwise conflicting), we present a simple 3/2-approximation algorithm.
Citation
Y. Cai, G. Chen, Y. Chen, R. Goebel, G. Lin, L. Liu, A. Zhang. "Approximation Algorithms for Two-machine Flow-shop Scheduling with a Conflict Graph". International Computing and Combinatorics Conference (COCOON), Qingdao, China, pp 205-217, July 2018.| Keywords: | Flow-shop scheduling, Conflict graph, b-matching, Path cover, Approximation algorithm |
| Category: | In Conference |
| Web Links: | Springer |
BibTeX
@incollection{Cai+al:(COCOON)18,
author = {Yinhui Cai and Guangting Chen and Yong Chen and Randy Goebel and
Guohui Lin and Longcheng Liu and An Zhang},
title = {Approximation Algorithms for Two-machine Flow-shop Scheduling with a
Conflict Graph},
Pages = {205-217},
booktitle = {International Computing and Combinatorics Conference (COCOON)},
year = 2018,
}Last Updated: June 09, 2020Submitted by Sabina P
