Just-in-time scheduling problem with affine idleness cost

We study a single-machine scheduling problem which minimizes total earliness, tardiness and idleness costs. In this problem, n jobs with job-specific due dates and processing times need to be processed in a non-preemptive fashion. We assume that when the idle time between two jobs is strictly positive, an idleness cost will be generated which is affine in the idle time. A hybrid solution approach is designed by integrating a tailored dynamic programming (TDP) algorithm for the exact timing solution and a customized Genetic Algorithm with restarts and early discarding (GARED) as the sequencing heuristic. By bounding the number of segments of the optimal cost function, we show that the proposed TDP algorithm has a low time complexity of O(n2) despite the non-convexity of the idleness cost function. In GARED, we utilize the monotonicity in the optimal cost in TDP to design a fast-screening scheme called Early Discarding which identifies and abandons an unpromising sequencing solution by evaluating only a short starting sub-sequence. Restarts are allowed to make the algorithm more robust in the case of premature local convergence of one evolutionary trial. Experimental results show that GARED significantly outperforms the basic elitist GA with or without restarts under most problems tested. Our hybrid method also scales well to large problem instances with n=300 and achieves similar or better performance compared to an exact algorithm in the literature, but the latter only applies to problems with integer-valued time parameters and no idleness cost in between the jobs.