Abstract
We consider a single-machine scheduling problem with equal-sized jobs. The objective is to minimize the maximum weighted earliness-tardiness and due-date costs. We present an algorithm to solve this problem. Our algorithm makes use of bottleneck jobs and priority queues, and has a computational complexity of O (n4 log n). This complexity is a significant improvement of the existing algorithm in the literature. © 2007 Elsevier Ltd. All rights reserved.
| Original language | English |
|---|---|
| Pages (from-to) | 3612-3619 |
| Journal | Computers and Operations Research |
| Volume | 35 |
| Issue number | 11 |
| DOIs | |
| Publication status | Published - Nov 2008 |
| Externally published | Yes |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Funding
The authors would like to thank two anonymous referees for their helpful comments and suggestions. This research was supported in part by the Recanati Fund of The School of Business Administration, The Hebrew University, Jerusalem, Israel and by Grant PolyU 5222/06E from the Hong Kong Research Grants Council.
Research Keywords
- Analysis of algorithms
- Due-date assignment
- Earliness-tardiness
- Scheduling
RGC Funding Information
- RGC-funded
Fingerprint
Dive into the research topics of 'An efficient algorithm for minimizing earliness, tardiness, and due-date costs for equal-sized jobs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver