Single-Machine Scheduling with Exponential Processing Times and General Stochastic Cost Functions |
| |
Authors: | Xiaoqiang Cai Xian Zhou |
| |
Institution: | (1) Department of Systems Engineering & Engineering Management, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong;(2) Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong |
| |
Abstract: | We study a single-machine stochastic scheduling problem with n jobs, in which each job has a random processing time and a general stochastic cost function which may include a random due date and weight. The processing times are exponentially distributed, whereas the stochastic cost functions and the due dates may follow any distributions. The objective is to minimize the expected sum of the cost functions. We prove that a sequence in an order based on the product of the rate of processing time with the expected cost function is optimal, and under certain conditions, a sequence with the weighted shortest expected processing time first (WSEPT) structure is optimal. We show that this generalizes previous known results to more general situations. Examples of applications to practical problems are also discussed.This work was partially supported by the Research Grants Council of Hong Kong under Earmarked Grants No. CUHK4418/99E and No. PolyU 5081/00E. |
| |
Keywords: | Due dates Exponential processing times Single machine Stochastic cost functions Stochastic scheduling |
本文献已被 SpringerLink 等数据库收录! |
|