Stochastic single-machine scheduling with random resource arrival times
- PDF / 1,396,694 Bytes
- 7 Pages / 595.276 x 790.866 pts Page_size
- 71 Downloads / 192 Views
ORIGINAL ARTICLE
Stochastic single‑machine scheduling with random resource arrival times Lianmin Zhang1 · Yizhong Lin2 · Yujie Xiao3 · Xiaopeng Zhang4
Received: 13 March 2016 / Accepted: 27 December 2016 / Published online: 28 January 2017 © Springer-Verlag Berlin Heidelberg 2017
Abstract Scheduling in an uncertain environment remains a meaningful yet challenging direction of research. In this paper, we consider a new scheduling setting from practical complex business applications, where resources (e.g., raw materials) used for processing jobs arrive randomly, due to reasons such as unstable transportation service caused by extreme weather conditions, unreliable suppliers, unpredictable industrial actions, etc. Further, jobs must be processed one by one and preemption is not allowed. The processing times of jobs are not known but their distribution. We incorporate these factors into a stochastic single-machine scheduling model and examine two different common types of objectives: minimizing total expected weighted completion time and minimizing total expected weighted squared completion time. We derive and prove a natural and intuitive optimal policy for the model * Yujie Xiao [email protected]; [email protected] Lianmin Zhang [email protected] Yizhong Lin [email protected] Xiaopeng Zhang [email protected] 1
School of Management and Engineering, Nanjing university, Nanjing 210093, China
2
School of Business, Jiaxing University, Jiaxing 314001, China
3
Jiangsu Key Laboratory of Modern Logistics, School of Marketing and Logistic Management, Nanjing University of Finance and Economics, Nanjing 210046, China
4
School of Business Administration, Zhejiang Gongshang University, Hangzhou 310018, China
with the first objective. Besides, we find that, under some mild conditions, the well-known policy in stochastic scheduling, WSEPT (weighted shortest expected processing time), still holds optimal for achieving either of objectives. The numerical example further supports and illustrates our results, which provide decision-makers insights into tricky uncertain scheduling problems. Keywords Stochastic scheduling · Completion times · Squared completion time
1 Introduction Scheduling, as a major field of the operational research discipline, has attracted attention both from industry and academia in the past few decades. Lots of scheduling models together with efficient algorithms have been proposed. Meanwhile, scheduling has apparent applications in various practical problems, including, for example, manufacturing and service, compiler optimization and parallel computing. Unfortunately, the vast majority of scheduling problems that we encounter in the real life are full of uncertainties (which arise from the unpredictability of future events, the lack of information among the participants, etc.) and scheduling under uncertainties remains a very meaningful yet challenging direction of research. In this paper, we study the stochastic single-machine scheduling problem from practical complex busine
Data Loading...
