Abstract
We consider the problem of scheduling jobs consisting of two part types in a shop made up of three machines. The processing of each job comprises two stages. The first stage is undertaken on the machine common to all jobs and the second stage is undertaken on the machine specific to a particular part type. Set-up times are necessary at the first stage to switch processing from a job of one part type to a job of the other part type. Jobs of the same part type processed contiguously at the first stage form a batch. The objective is to find a batch schedule minimizing the makespan. An integer programming formulation and a heuristic algorithm for this problem have been reported in the literature. We present a dynamic programming algorithm which solves the problem optimally in a time polynomial in the number of jobs.
| Original language | English |
|---|---|
| Pages (from-to) | 53-56 |
| Number of pages | 4 |
| Journal | International Journal of Production Economics |
| Volume | 55 |
| Issue number | 1 |
| Publication status | Published - 10 Jun 1998 |
Keywords
- Batching
- Scheduling
ASJC Scopus subject areas
- General Business,Management and Accounting
- Economics and Econometrics
- Management Science and Operations Research
- Industrial and Manufacturing Engineering