|
| << vorige |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 9 van 9 gevonden artikelen
| Titel: |
Some results on resource constrained scheduling |
| Auteur: |
Zhang, Guochuan Cai, Xiaoqiang Wong, C. K. |
| Verschenen in: |
IIE transactions |
| Paginering: | Jaargang 36 (2004) nr. 1 pagina's 1-9 |
| Jaar: |
2004-01 |
| Inhoud: |
We consider a variant of the resource constrained scheduling problem, which originated from a machine scheduling problem. A number of jobs are to be processed on a single machine with a prespecified capacity. Each job has a size and a processing time, and the machine can process a set of jobs simultaneously as long as the total size of the jobs being processed does not exceed the capacity of the machine. The objective is to find a schedule to minimize the total time (i.e., the makespan) to complete all jobs, subject to the machine capacity constraint. For the problem where the machine is completely available at the starting time, we analyze a previously published algorithm and prove that the worst-case ratio of this algorithm is no more than 7/4, which significantly improves the previous result and thus answers an open question about this algorithm. For the problem where the machine is partially available at the beginning, an algorithm is shown to have a worst-case ratio of no more than two. An on-line algorithm is also presented. |
| Uitgever: |
Taylor & Francis |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 9 van 9 gevonden artikelen
| << vorige |