Preemptive Open-Shop Scheduling: Network Flow Based Algorithm

Abstract:

Article Preview

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.

Info:

Periodical:

Edited by:

Congda Lu

Pages:

111-114

DOI:

10.4028/www.scientific.net/AMR.215.111

Citation:

Y. Zhan et al., "Preemptive Open-Shop Scheduling: Network Flow Based Algorithm", Advanced Materials Research, Vol. 215, pp. 111-114, 2011

Online since:

March 2011

Export:

Price:

$35.00

In order to see related information, you need to Login.

In order to see related information, you need to Login.