Scheduling with Hierarchies and Overload Cost

In this paper, we consider the problem of scheduling with hierarchies and overload cost (SHOC). Given a set of jobs \(\mathcal{J} =\{J_1,\ldots ,J_n\}\) , a set of two hierarchical identical parallel machines \(\mathcal{M}=\{M_1,M_2\}\) , a processing time function p and a hierarchy function g on the job set \(\mathcal J\) , a regular working time \(L_0\) of the machines, a start-up cost \(c_0\) and a cost \(c_1\) of per unit overload, and the hierarchies of the machines \(M_1\) and \(M_2\) are 1 and 2 respectively. Each machine can only process the jobs whose hierarchies are no less than the hierarchy of this machine. We are asked to assign all jobs of \(\mathcal{J}\) to the machines \(M_1\) and \(M_2\) , and if the total processing time \(L_i\,(i=1,2)\) of any machine is more than \(L_0\) , a charge of \(c_1\) should be paid for per unit overload. The objective is to minimize the total cost of processing all the jobs. We design a \(1+\frac{1}{20}c_1/c_0\) -approximation algorithm to solve our problem by using the LPT method. And based on four characteristics of optimal solutions and two dynamic programmings, we give a pseudo-polynomial time algorithm to find an optimal solution in \(\mathcal{O}(nL_0)\) time.