On the Hardness of Edge Coloring Problems Associated with Scheduling

In this work, we introduce several Edge Coloring problems related to scheduling and we study their computational complexity. In particular, we prove that the Concurrent Open Shop Coloring is NP-hard. This problem can be summarized as a unitary-time Open Shop Problem with a hard time horizon constraint, in which the goal is to minimize the total processing time of the tasks. We prove that this problem is NP-hard by reducing it to a new variant of the edge coloring problem, named the Mono-Polychromatic Edge Coloring. We study the feasibility and hardness of this problem, both for the general case and when the underlying graph is bipartite. We show that the latter case is equivalent to the Vertex Coloring Problem.