Algorithms for the joint multitasking scheduling and common due date assignment problem

Abstract

In this paper, we investigate a joint multitasking scheduling and common due date assignment problem on a single machine, for which examples can be found in product delivery process in logistics. Multitasking allows the machine to perform multiple tasks. The multitasking phenomenon has been observed in various practical domains, including manufacturing and administration. In multitasking settings, each waiting job interrupts a currently in-processing job, causing an interruption time and a switching time. In common due date assignment problems, the objective is to determine the optimal value of this due date with the purpose of minimising a total penalty function, which is associated with service quality. For the problem with general interruption functions, analytical properties are obtained to reduce the search space of the optimal solutions. For the cases with linear interruption functions, we develop a polynomial-time algorithm. Numerical experiments have been conducted to validate the efficiency of our proposed algorithm. Computational results also demonstrate an interesting phenomenon that in some cases, the optimal solutions under multitasking are superior to the counterparts without multitasking. Besides, we also devise a mixed integer programme for the cases with linear interruption function.

Keywords:

• scheduling
• common due date assignment
• multitasking scheduling
• mixed integer programming
• polynomial-time algorithm

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [grant number 71531011], [grant number 71571134], [grant number 71571135], [grant number 71432007], [grant number 71428002]; the Cai Yuanpei Program between the French Ministries of Foreign and European Affairs. This work was also sponsored by the Fundamental Research Funds for the Central Universities, and Shanghai Pujiang Program.