Loading...
Please wait, while we are loading the content...
Similar Documents
Scheduling two groups of jobs with incomplete information
| Content Provider | Semantic Scholar |
|---|---|
| Author | Zhang, Guochuan Cai, Xiaoqiang Wong, C. K. |
| Copyright Year | 2003 |
| 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. |
| Starting Page | 73 |
| Ending Page | 81 |
| Page Count | 9 |
| File Format | PDF HTM / HTML |
| DOI | 10.1007/s11518-006-0121-y |
| Volume Number | 12 |
| Alternate Webpage(s) | https://page-one.springer.com/pdf/preview/10.1007/s11518-006-0121-y |
| Alternate Webpage(s) | http://www.rccm.tsinghua.edu.cn/JSSSE/samples/file-5-caixiaoqiang.pdf |
| Alternate Webpage(s) | https://doi.org/10.1007/s11518-006-0121-y |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
