Heuristics for scheduling problems on identical machines like storage allocation

In this paper, we consider a combinatorial optimization problem of scheduling n jobs of block type on linearly aligned m identical machines. Each job J_j is characterized by four integers, an arrival time a_j , a processing time p_j, the number q_j of consecutive machines required by the job (hence, each job J_j can be represented by a rectangular block with the size of p_j × q_j in a geometrical interpretation), and a weight w_j. There is a choice for each job whether the aligned machines serve it or not. If the aligned machines choose (i.e., serve) a job J_j, they gain the weight w_j as their profit. However, they have to start the service of the chosen job promptly after it arrives (i.e., they have to start the service exactly at time t = a_j ), selecting q_j consecutive machines in the alignment. Every machine can handle at most one job at a time, and no preemption is allowed for the services of jobs. The objective is to find a feasible schedule that maximizes the weighted number of chosen jobs. It has already been known that the scheduling problem is NP-hard for an arbitrary m. In this paper, we propose a polynomial time heuristic algorithm based on a transformation into the minimum cost flow problem, and prove that the approximation ratio is ⌊m/q_min⌋ / ⌊m/q_max⌋, where q_min = min_{1 ≤ j ≤ n}{q_j} and q_max = max_{1 ≤ j ≤ n}{q_j}.