## Abstract

We consider the problem of scheduling n jobs on m ≥ 1 parallel and identical machines, where the jobs are processed in batches and the processing time of each job is a step function of its waiting time; i.e., the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. For each job i, if its waiting time is less than a given threshold D, then it requires a basic processing time p_{i} = a_{i}; otherwise, it requires an extended processing time p_{i} = a_{i} + b_{i}. The objective is to minimize the sum of completion times; i.e., ∑_{i = 1}^{n} C_{i}, where C_{i} is the completion time of job i. We first show that the problem is NP-hard in the strong sense even if there is a single machine and b_{i} = b for all 1 ≤ i ≤ n. We then show that the problem is solvable in polynomial time if a_{i} = a for all 1 ≤ i ≤ n. Our algorithm runs in O(n^{2}) time. Finally, we give an approximation algorithm for the special case where b_{i} ≤ D for all 1 ≤ i ≤ n, and show that it has a performance guarantee of 2.

Original language | English (US) |
---|---|

Pages (from-to) | 1090-1099 |

Number of pages | 10 |

Journal | European Journal of Operational Research |

Volume | 187 |

Issue number | 3 |

DOIs | |

State | Published - Jun 16 2008 |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- Modeling and Simulation
- Management Science and Operations Research
- Information Systems and Management

## Keywords

- Batch scheduling
- Deteriorating processing times
- Performance guarantee
- Strong NP-hardness
- Sum of completion times