Open shop scheduling problems with late work criteria

The paper concerns the application of a non-classical performance measure, a late work criterion (Y, Y-w), to scheduling problems. It estimates the quality of the obtained solution with regard to the duration of the late parts of tasks not taking into account the quantity of this delay. The paper provides the formal definition of the late work parameter, especially in the shop environment, together with its practical motivation. It contains general complexity studies and the results of investigating open-shop scheduling cases, i.e. two polynomial time algorithms for problems 0 \ pmtn, r(i) \ Y-w and O2 \ d(i) = d \ Y, as well as the binary NP-hardness proof for O2 \ d(i) = d \ Y-w. (C) 2003 Elsevier B.V. All rights reserved.