| SCHEDULING TWO GROUPS OF JOBS WITH INCOMPLETE INFORMATION |
| |
| 引用本文： | C.K.WONG. SCHEDULING TWO GROUPS OF JOBS WITH INCOMPLETE INFORMATION[J]. 系统科学与系统工程学报(英文版), 2003, 12(1): 73-81. DOI: 10.1007/s11518-006-0121-y |
| |
| 作者姓名： | C.K.WONG |
| |
| 作者单位： | On leave |
| |
| 基金项目： | Research partially supported by a Hong Kong Government RGC Earmarked Grant.Ref.No.CUHK356/96E Research partially supported by National 973 Fundamental Research Project of china and National Natural Science Foundation of China (19801032) |
| |
| 摘 要： | In real world situations, most scheduling problems occur neither as complete off-line nor ascomplete on-line models. Most likely a problem arises as an on-line model with some partialinformation. In this article, we consider such a model. We study the scheduling problem P(n_1,n_2),where two groups of jobs are to be scheduled. The first job group is available beforehand. As soon asall jobs in the first group are assigned, the second job group appears. The objective is to minimize thelongest job completion time(makespan). We show a lower bound of 3/2 even for very special cases.Best possible algorithms are presented for a number of cases. Furthermore, a heuristic is proposed forthe general case. The main contribution of this paper is to discuss the impact of the quantity ofavailable information in designing an on-line algorithm. It is interesting to note that the absence ofeven a little bit information may significantly affect the performance of an algorithm.
|
| 关 键 词： | 编制 机床作业进度表 不完全信息 最坏情况分析 在线运算 |
Scheduling two groups of jobs with incomplete information |
| |
| Guochuan Zhang,Xiaoqiang Cai,C. K. Wong. Scheduling two groups of jobs with incomplete information[J]. Journal of Systems Science and Systems Engineering, 2003, 12(1): 73-81. DOI: 10.1007/s11518-006-0121-y |
| |
| Authors: | Guochuan Zhang Xiaoqiang Cai C. K. Wong |
| |
| Affiliation: | Department of Mathematics,Zhejiang University Hangzhou 3 0027, PR. China;Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong Shatin, N. T., Hong Kong; Department of Computer Science and Engineering, The Chines |
| |
| Abstract: | In real world situations, most scheduling problems occur neither as complete off-line nor as complete on-line models. Most likely, a problem arises as an on-line model with some partial information. In this article, we consider such a model. We study the scheduling problem P(n1,n2), where two groups of jobs are to be scheduled. The first job group is available beforehand. As soon as all jobs in the first group are assigned, the second job group appears. The objective is to minimize the longest job completion time (makespan). We show a lower bound of 3/2 even for very special cases. Best possible algorithms are presented for a number of cases. Furthermore, a heuristic is proposed for the general case. The main contribution of this paper is to discuss the impact of the quantity of available information in designing an on-line algorithm. It is interesting to note that the absence of even a little bit information may significantly affect the performance of an algorithm. |
| |
| Keywords: | Machine scheduling worst-case analysis on-line algorithm |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
