Scheduling stochastic jobs on a single machine to minimize weighted number of tardy jobs

Kuwait Journal of Science

H. M. SOROUSH¹ 

[1] Department of Statistics and Operations Research, Kuwait University, P. O. Box 5969, Safat 13060, Kuwait

关键词: Number of tardy jobs;    scheduling;    single machine;    stochastic.;   

DOI  :  

学科分类：社会科学、人文和艺术（综合）

来源: Kuwait University * Academic Publication Council

【 摘 要 】

ABSTRACT An important scheduling problem in manufacturing and service organizations is the on-time deliveries of products and services. This paper addresses a single machine scheduling problem wherein processing times and/or due-dates are random variables and fixed weights (penalties) are imposed on late jobs. The objective is to find the schedule that minimizes the expected weighted number of tardy jobs. The problem is NP-hard; however, we study the three resulting scenarios: the scenario with stochastic processing times and stochastic due-dates, the scenario with deterministic processing times and stochastic due-dates, and the scenario with stochastic processing times and deterministic due-dates. We prove that special cases of these scenarios are solvable optimally in polynomial time, and introduce heuristic methods for their general cases. Our computational results show that the proposed heuristics perform well in producing the optimal or near optimal solutions. The illustrative examples and computational results also demonstrate that the stochasticity of processing times and/or due-dates can affect scheduling decisions.  

【 授权许可】

Unknown