Minimizing the weighted number of late jobs in UET open shops

We consider a two-machine open shop problem where the jobs have release dates and due dates, and where all single operations have unit processing times. The goal is to minimize the weighted number of late jobs. We derive a polynomial time algorithm for this problem, thereby answering an open question posed in a recent paper by Brucker et al.This research was supported by the Christian Doppler Laboratorium für Diskrete Optimierung.