¹The Hebrew University, Jerusalem 91905, Israel

Correspondence: G Mosheiov, Department of Statistics and School of Business Administration, 3, The Hebrew University, Mount Scopus, Jerusalem 91905, Israel. E-mail: msomer@mscc.huji.ac.il

Received February 2003; Accepted July 2003.

Abstract

The problem of minimizing the maximal weighted absolute lateness (MWAL) is known to be NP-hard. The due-date assignment part of MWAL for a given sequence has been shown in the literature to be solved on a single machine in O(n²) time. In this paper, we study a more general version of the problem with asymmetric cost (nonidentical earliness and tardiness weights). We introduce a linear-programming-based O(n) solution for this case. We also extend our proposed solution procedure to other machine settings such as flow-shop and parallel machines.