Scheduling about an unrestricted common due window with arbitrary earliness/tardiness penalty rates

Azizoglu M., Webster S.

IIE TRANSACTIONS, cilt.29, sa.11, ss.1001-1006, 1997 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 29 Sayı: 11
  • Basım Tarihi: 1997
  • Doi Numarası: 10.1080/07408179708966418
  • Dergi Adı: IIE TRANSACTIONS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.1001-1006
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due window to minimize total weighted earliness and tardiness cost. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. Earliness or tardiness cost is assessed when a job completes outside the due window, which may be an instant in time or a time increment defining acceptable job completion. In this paper we present properties that characterize the structure of an optimal schedule, present a lower bound, propose a two-step branch and bound algorithm, and report results from a computational experiment. We rnd that optimal solutions can be quickly obtained for medium-sized problem instances.