In the known Interval Scheduling problem with Machine Availabilities (ISMA), each machine has a contiguous availability interval, and each job has a specific time interval which has to be scheduled. The objective is to schedule all jobs such that the machines’ availability intervals are respected or to decide that there exists no such schedule. We extend ISMA by introducing machine capacities and flexible machine end times. Using machine capacities we model parallel processing of multiple jobs per machine, which leads to the Multithread Interval Scheduling with Machine Availabilities (MISMA). Limited machine availabilities are usually due to maintenance. Time slots for maintenance at the end of a processing period are often predetermined by staff schedules before the slots are assigned to specific machines. This motivates a variant of MISMA in which the end times of the machines’ availability intervals can be permuted, the Flexible Multithread ISMA (FLEXMISMA). In this paper, we determine a tight classification of conditions that are required for obtaining a polynomial-time algorithm for both MISMA and FLEXMISMA. More specifically, we show that FLEXMISMA is at least as hard as MISMA. For FLEXMISMA, we present polynomial-time algorithms for instances (i) with at most two available machines at a time, and (ii) with constantly many parallel jobs at each point in time, which both also solve MISMA; (iii) with arbitrarily many machines of capacity one each, in which case MISMA is known to be NP-hard; and (iv) with jobs having length one or two, for which the complexity of MISMA remains open Furthermore, we complement result (i) by showing that both problems are NP-hard already for instances with three machines as a special case of the Vertex-Disjoint Paths problem. In contrast to (iii), we prove that increasing the capacity of machines from one to two renders FLEXMISMA NP-hard as well for arbitrarily many machines.

Abstract The minimum color‐degree perfect b‐matching problem (Col‐BM) is a new extension of the perfect b‐matching problem to edge‐colored graphs. The objective of Col‐BM is to minimize the maximum number of differently colored edges in a perfect b‐matching that are incident to the same node. We show that Col‐BM is ‐hard on bipartite graphs by a reduction from (3,B2)‐Sat, and conclude that there exists no (2 − ϵ)‐approximation algorithm unless . However, we identify a class of two‐colored complete bipartite graphs on which we can solve Col‐BM in polynomial time. Furthermore, we use dynamic programming to devise polynomial‐time algorithms solving Col‐BM with a fixed number of colors on series‐parallel graphs and simple graphs with bounded treewidth.