Due-date assignment scheduling with only mean and support of processing times

Abstract

We consider a single-machine scheduling problem with due-date assignment and stochastic processing times, where only the mean and support (i.e. an interval bounded with lower and upper values) of processing times are known to the decision maker. The objective is to jointly determine a scheduling policy and a set of due dates for all jobs, so as to minimise the total expected individually weighted costs of earliness, tardiness and due-date assignment. By identifying an upper bound with the robust optimisation approach and a lower bound, and using a linear function of them to approximate the studied objective function, we establish an approximated problem. Then, a branch-and-bound algorithm is proposed to find an optimal solution for the approximated problem. Finally, a series of computational experiments are conducted to examine the performance of problem approximation and two developed heuristic algorithms.

HIGHLIGHTS

• Study due-date assignment scheduling problem with stochastic processing times.

• Apply the mean and support (interval data) to model stochastic processing times.

• Use a linear function of identified lower and upper bounds to make an approximation.

• Derive optimal due-date assignment and develop branch-and-bound algorithms.

• Evaluate the efficiency of branch-and-bound algorithm and heuristic algorithms.

KEYWORDS:

• Due-date assignment
• scheduling
• the mean and support
• stochastic processing times
• approximation

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data that support the findings of this study are openly available in figshare at https://figshare.com/articles/dataset/data-Qing_Yue_xlsx/20188349.

Additional information

Funding

The first author is supported by the National Natural Science Foundation of China (NSFC, No. 72101142), the second author is supported in part by NSFC (No. 72101102), the Humanities and Social Sciences Project of the Ministry of Education (No. 21YJC630179), the Key Program for National Social Science Foundation of China (No. 21AZD117), the Major Program of National Natural Science Foundation of China (No. 71991463) and the Foundation of Xiangjiang Lab (No. 22XJ03025).

Notes on contributors

Qing Yue

Qing Yue is an Associate Professor at the School of Management, Shanghai University of International Business and Economics. She received his PhD degree in Management Science and Engineering from Shanghai Jiao Tong University, Shanghai, China, in 2016. Her research interests include supply chain scheduling and data-driven operations research. She has published in journals such as IISE Transactions, European Journal of Operational Research, Journal of the Operational Research Society, International Journal of Production Research, Computers and Operations Research and others.

Shenghai Zhou

Shenghai Zhou is a Distinguished Associate Professor at the School of Business, Central South University. He received his PhD degree in Management Science and Engineering from Shanghai Jiao Tong University, Shanghai, China, in 2019. His research interests lie in stochastic programming with particular interests in appointment scheduling and operating room scheduling and healthcare operations management. His research works have been published in Production and Operations Management, European Journal of Operational Research, OMEGA, International Journal of Production Research, Computers and Operations Research and others.

Haiyan Yan

Haiyan Yan is an Associate Professor at the School of Management, Shanghai University of International Business and Economics. She received her PhD degree in Management Science and Engineering from Tongji University, Shanghai, China, in 2010. Her research interests lie in supply chain and operations management with particular interest in the application of system dynamics. Her research works have been published in Chinese Journal of Systems Science and others.