A note on pre-emptive scheduling with earliness and tardiness costs |
| |
Authors: | GUR MOSHEIOV |
| |
Institution: | School of Business Administration, and Department of Statistics , The Hebrew University , Jerusalem, Israel. |
| |
Abstract: | The option of pre-emption seems to have escaped the attention of existing literature on scheduling problems with earliness and tardiness costs. This note presents an attempt to accommodate pre-emption in such settings. The focus is on models with a common due date for all jobs under different cost structures ( job dependent versus job independent), and different objectives ( minsum and minmax). It appears that only one of these cases is not polynomially solvable: the case of minsum objective and job-dependent ( linear) cost. An exact dynamic programming algorithm is introduced for this problem, as well as an efficient heuristic, which is shown to perform extremely well in our numerical tests. |
| |
Keywords: | deterministic scheduling earliness and tardiness costs pre-emption heuristics |
|
|