Single-machine scheduling with autonomous and induced learning to minimize total weighted number of tardy jobs

As commonly observed in practice, firms can accelerate job processing by adding additional resources to the manufacturing system while striving to sustain on-time delivery. In this paper we consider due date assignment and scheduling with a learning effect that can be invoked by proactive investment at the beginning, known as induced learning in the literature. The objective is to find the optimal decisions on due date assignment, job sequencing, and level of induced learning to minimize a cost function consisting of the total weighted number of tardy jobs, due date penalty, and investment cost. We find a novel property of the optimal solution that although the due date penalty may be larger, the number of on-time jobs will not decrease with the increasing induced learning effect, which is a breakthrough to solve the problem. Exploiting the property, we present a polynomial-time algorithm that generates an approximation solution with a gap less than Lϵ compared with the optimal result, where ϵ can tend to be infinitesimal, and L is a constant.