COMMON DUE-DATE ASSIGNMENT AND SCHEDULING FOR A SINGLE PROCESSOR TO MINIMIZE THE NUMBER OF TARDY JOBS

Abstract

This paper considers the problem of assigning a common due-date to a set of simultaneously available jobs and sequencing them on a single production facility. The objective is to determine the optimal common due-date value and job sequence that jointly minimize a cost function based on the assigned due-date and the number of tardy jobs. It is shown that the optimal due-date coincides with one of the job completion times and ordering jobs in non-decreasing processing times yields an optimal sequence which in general is not unique. An efficient (polynomial-bound) algorithm to find the optimal solution is presented and an illustrative example is provided.

KEY WORDS:

• Due-dates
• assignment
• scheduling
• job-shops
• manufacturing
• production