A note on the two machine job shop with the weighted late work criterion

What is it about?

This paper presents a dynamic programming approach for the two-machine nonpreemptive job-shop scheduling problem with the total weighted late work criterion and a common due date, which is known to be NP-hard. The late work performance measure estimates the quality of an obtained solution with regard to the duration of late parts of tasks not taking into account the quantity of this delay. Providing a pseudopolynomial time method for the problem mentioned we can classify it as binary NP-hard.

Featured Image