Back to Search
Start Over
Preemptive Open-Shop Scheduling: Network Flow Based Algorithm
- Source :
- Advanced Materials Research. 215:111-114
- Publication Year :
- 2011
- Publisher :
- Trans Tech Publications, Ltd., 2011.
-
Abstract
- Preemptive open-shop scheduling problem was studied, and a network flow based algorithm was presented. Firstly, based on the characteristics of the preemptive open-shop, the scheduling problem was formulated as a mixed-integer programming model with the objective to minimize the make-span. The maximum flow model of the preemptive open-shop was developed to model the machine resource allocation and time constraints. Moreover a new preflow push algorithm for the maximum flow model was put forward. Based on the solution of machine resource allocation problem got by preflow push algorithm, the sequences of the tasks processed by each machine were determined by calculating the matrix of the processing times and decrementing set. Finally, the validity of the developed scheduling algorithm is illustrated by randomly generated example.
- Subjects :
- Rate-monotonic scheduling
Push–relabel maximum flow algorithm
Open-shop scheduling
Job shop scheduling
Computer science
Maximum flow problem
General Engineering
Dynamic priority scheduling
Flow shop scheduling
Flow network
Fair-share scheduling
Scheduling (computing)
Fixed-priority pre-emptive scheduling
Resource allocation
Algorithm
Subjects
Details
- ISSN :
- 16628985
- Volume :
- 215
- Database :
- OpenAIRE
- Journal :
- Advanced Materials Research
- Accession number :
- edsair.doi...........03e645fd3d907208296a9a5ee7c7b2a2