| Article ID: | iaor20043071 |
| Country: | United Kingdom |
| Volume: | 31 |
| Issue: | 5 |
| Start Page Number: | 645 |
| End Page Number: | 655 |
| Publication Date: | Apr 2004 |
| Journal: | Computers and Operations Research |
| Authors: | Mosheiov Gur, Oron Daniel |
| Keywords: | heuristics |
Two NP-hard scheduling problems on parallel identical machines with generalized due dates are studied. We focus on two objectives: (i) minimizing maximum tardiness and (ii) minimizing total tardiness. In both cases, we introduce a shortest processing time first (SPT)-based heuristic and simple lower bounds on the optimal cost. Our numerical study indicates that the SPT heuristic performs extremely well in all settings.