An approximation algorithm for the license and shift class design problem

In this paper a generalization of the license and shift class design problem is considered. Let J be a set of jobs which have to be carried out in specified time intervals, let E be a set of different engineer licenses and Z be a set of shifts. Given a price P(e,z)∈ℝ’+ for engineers with licence e∈E assigned to shift z∈Z, the problem is to find numbers of engineers to carry out all jobs with minimum cost. An approximation algorithm with time complexity O(∈E∈ë∈Z∈ë∈J∈²) and approximation bound O(log∈J∈) is proposed for this problem.