A family of multiclass LCFS networks with a novel product-form solution

Abstract We study two-station closed queueing network models where jobs cyclically visit a non-preemptive last-come first-serve (LCFS-NP) station and a last-come first-serve preemptive-resume (LCFS-PR) station. Jobs belong to multiple classes and receive at both stations exponential service times with arbitrary means. Even though multiclass LCFS-NP stations are not quasi-reversible, we show that the considered models still admit a product-form solution. A feature of the new product-form expression is to include factors that relate the mean service times at the LCFS-NP queue with the positions occupied by the jobs at both stations. To account for job positions, we propose a strategy to compute the normalizing constant of the state probabilities using permanents which, for a fixed number of classes, solves the model exactly in polynomial time as the total number of jobs grows. A mean-value analysis algorithm is also derived, using a recursion on networks where the job holding the last position at the LCFS-PR queue is removed from the model.