Time-Flexible Min Completion Time Variance in a Single Machine by Quadratic Programming

In the context of job scheduling, the time required to complete a task is related not only to the intrinsic difficulty of the task, but also to the operator's willingness to speed up (or slow down) its execution. In fact, service operators are sometimes authorized to flexibly calibrate job processing times when this is beneficial for the efficient design of services and production plans. In this paper, we show that some forms of time flexibility have major consequences on the operator's ability to efficiently solve the problem of scheduling non-preemptive jobs to minimize the variance of their completion times. In fact, while this is a difficult combinatorial problem, authorizing forms of processing time flexibility implies the possibility to solve it by convex quadratic programming approaches to tackle large-scale instances, where no exact algorithm can be applied. Our contribution is to establish the least flexibilization of job processing times while guaranteeing the solvability of the resulting problem by convex quadratic programming approaches. To this end, we provide novel bounding conditions for the characterization of an optimal sequence that strengthen and integrate the results of Nasini & Nessah (2021) and Manna & Prasad (1999). Our numerical tests indicate that this new methodology is capable of approaching the solution of the original min completion time variance problem with a max relative difference of about $0.05\%$ (on average), with respect to the time-flexible solution