全局信息不全的动态调度问题基于虚拟调度的两级滚动方法.pdf

Vol.32, No.1ACTA AUTOMATICA SINICAJanuary, 2006Two-level Rolling Procedure Based on Dummy Schedule for Dynamic Scheduling Problem with Incomplete Global Information1)WANG Bing1,2XI Yu-Geng21(School of Information Engineering, Shandong University at Weihai, Weihai264209) 2(Institute of Automation, Shanghai Jiaotong University, Shanghai200030) (E-mail: wangbing@)AbstractThis paper addresses the single-machine scheduling problem with release times mini- mizing the total completion time. Under the circumstance of incomplete global information at each decision time, a two-level rolling scheduling strategy (TRSS) is presented to create the global schedule step by step. The estimated global schedules are established based on a dummy schedule of unknownjobs. The first level is the preliminary scheduling based on the predictive window and the second level is the local scheduling for sub-problems based on the rolling window.Performance analysis demonstrates that TRSS can improve the global schedules. Computational results show that the solution quality of TRSS outperforms that of the existing rolling procedure in most cases.Key wordsTwo-level rolling scheduling, dummy schedule, preliminary scheduling, local schedu- ling1Introduction Scheduling problems are sorted as deterministic and dynamic problems according to whether the global information about jobs and machines is known a priori or not. The optimal solution of dy- namic or large-size scheduling problem is impossibly obtained because of incomplete global information and computational complexity. When the predictive control principle[1]was extended to scheduling problems, the rolling horizon scheduling procedures[2∼6], which can just deal with computational com- plexity and uncertain information, were developed. In [2], a generic rolling scheduling mechanism based on initial schedule was established and the global performances were analyzed, however, the discussed scheduling circumstance was deterministic. In fact, for dynamic scheduling problems with release times, jobs arriving in further future are usually unknown at decision moments due to the incomplete global information. Rolling horizon procedures (RHPs) addressed such dynamic circumstance based on localoptimal sub-problems in [3] and the computational results show effective. However, the solutions are sometimes bad due to no global performance analysis.It is difficult to analyze the global performances for dynamic scheduling in finite horizon.In this paper, we will extend the rolling mechanism of [2] to address dynamic scheduling problems with incomplete global information, present a kind of two-level rolling scheduling strategy, and analyze the global performances.2TRSS for dynamic 1/ri/ΣCi The scheduling problem model 1/ri/ΣCiindicates that n jobs are to be scheduled for a single machine to minimize the total completion time and each job has a release time riand a processing time pi. This problem is strongly NP-hard[7]. We assume that n is a finite integer. 2.1Dummy initial scheduleThe involved definitions and detail descriptions of rolling scheduling based on initial schedulewere presented in [2]. There are two stages, i.e., firstly an initial schedule is established for all jobs and secondly a rolling scheduling procedure is performed based on the initial schedule. At each decision mo- ment, the global schedule is transformed by the local scheduling. A schedule before the local scheduling is called a previous schedule and the one after the local scheduling is called the current schedule. Here the initial schedule provides not only a sequence of jobs entering rolling windows but also a base of formulating global schedules. It helps to analyze global performances.1) Supported by National Natural Science Foundation of P.R. China (60274013, 60474002), Shanghai Development Foundation for Science and Technology (04DZ11008), Science Research Foundation of Shandong University at Weihai (XZ2005001) Received November 3, 2004; in revised form October 14, 2005Copyright c? 2006 by Editorial Office of Acta Automatica Sinica. All rights reserved.10ACTA AUTOMATICA SINICAVol.32A global schedule will be unlikely specified in a dynamic scheduling problem until global informa- tion is completely known. At the beginning, when all jobs are unknown, we can create a dummy initial schedule, denoted as˜D.˜D is made by the dispatching rule FIFO (First in first operating), where jobs are sequenced from small to large in job release times as well as job processing times (whenever therelease times are the same). In a dummy schedule, a job is just a symbol and not specified until the job is predicted. Though any dispatching rules can be used to create a dummy schedule, only FIFO can make the job sequence consistent with the sequence of jobs to be predicted. This is important to the following analysis. We can provide an estimated schedule for unknown jobs based on dummy schedule so that global performances can be estimated。