### Abstract

We study a problem in which a set of n jobs has to be batched as well as scheduled for processing on a single machine. A constant machine set-up time is required before the first job of each batch is processed. A schedule specifies the sequence of batches, where each batch comprises a sequence of jobs. The batch delivery time is defined as the completion time of the last job in a batch. The earliness of a job is defined as the difference between the delivery time of the batch to which it belongs and the job completion time. The objective is to find a number B of batches and a schedule so as to minimize the sum of the total weighted job earliness and mean batch delivery time. The problem is shown to be strongly N P-hard. It remains strongly N P-hard if the set-up time is zero and B ≤ U for any variable U ≥ 2 or if B ≥ U for any constant U ≥ 2. The problem is proved to be ordinary N P-hard even if the set-up time is zero and B ≤ 2. For the case B ≤ U, a dynamic programming algorithm is presented, which is pseudopolynomial for any constant U ≥ 2. Algorithms with O(n^{2}) running times are derived for the cases when all weights are equal or all processing times are equal. For the general problem, a family of heuristics is suggested. Computational experiments on the proposed heuristic algorithm are conducted. The results suggest that the heuristics are effective in generating near-optimal solutions quickly.

Original language | English |
---|---|

Pages (from-to) | 547-559 |

Number of pages | 13 |

Journal | SIAM Journal on Optimization |

Volume | 7 |

Issue number | 2 |

DOIs | |

State | Published - 1 Jan 1997 |

### Keywords

- Batch scheduling
- Dynamic programming
- N P-hardness
- Polynomial algorithms
- Single machine scheduling

## Fingerprint Dive into the research topics of 'Single machine scheduling to minimize batch delivery and job earliness penalties'. Together they form a unique fingerprint.

## Cite this

*SIAM Journal on Optimization*,

*7*(2), 547-559. https://doi.org/10.1137/S1052623494269540