A Single Processor Scheduling Problem with a Common Due Window Assignment

Adam Janiak () and Marcin Winczaszek ()
Additional contact information
Adam Janiak: Wroclaw University of Technology
Marcin Winczaszek: Wroclaw University of Technology

A chapter in Operations Research Proceedings 2004, 2005, pp 213-220 from Springer

Abstract: Abstract We consider a single processor scheduling problem with a common due window assignment. Jobs completed within the due window incur no penalty, while other jobs incur either earliness or tardiness penalties. Boundaries of the due window are decision variables. The objective is to minimize the sum of the total weighted earliness, the total weighted tardiness and due window width penalty. This problem is an extension of the classical Weighted Earliness and Tardiness problem (WET). We proved that our problem is NP-hard and presented some properties of an optimal solution. To solve the problem we constructed a dynamic programming algorithm and a fully polynomial time approximation scheme. We also presented a polynomial time algorithm for the case with unit job processing times.

Date: 2005
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-540-27679-1_27

Ordering information: This item can be ordered from
http://www.springer.com/9783540276791

DOI: 10.1007/3-540-27679-3_27

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().