Single-machine parallel-batching scheduling with family jobs to minimize weighted number of tardy jobs

• A parallel-batching scheduling problem with uniform family due dates is considered.
• An FPTAS scheme is proposed for the weighed number of tardy jobs.
• An O(n2)O(n2)-time algorithm is provided for the unit weight problem.
• An O(nlogn)O(nlogn)-time algorithm is presented for the equal processing time problem.

We consider the problem of scheduling n   jobs in batches on a single parallel-batching machine, where the jobs are partitioned into jobs families and the jobs in each family have the same due date. The objective is to minimize the weighted number of tardy jobs. We first devise an efficient pseudo-polynomial time and a fully polynomial time approximation scheme for the weighted problem. Then we present O(n2)O(n2)-time and O(nlogn)O(nlogn)-time algorithms for the case where the jobs have the same weight and for the case where the jobs have the same processing time, respectively.