Prevent preempted arrivals exceed queue size

[nacnudus]

In the following system with a zero-length queue, the first arrival is preempted, waits in the zero-length queue for service, and is eventually served.

library(simmer)
p0 <- 
  create_trajectory("Low-priority trajectory") %>%
  seize("Finite queue server", priority = 0, preemptible = 0) %>%
  timeout(10) %>%
  release("Finite queue server")
p1 <- 
  create_trajectory("High-priority trajectory") %>%
  seize("Finite queue server", priority = 1, preemptible = 1) %>%
  timeout(10) %>%
  release("Finite queue server")
env <- 
  simmer() %>%
  add_generator("Low-priority arrival ", p0, at(0, 2)) %>%
  add_generator("High-priority arrival ", p1, at(1)) %>%
  add_resource("Finite queue server", queue_size = 0, preemptive = TRUE) %>%
  run()
env %>% get_mon_arrivals
#>                      name start_time end_time activity_time finished
#> 1  Low-priority arrival 1          2        2             0    FALSE
#> 2  Low-priority arrival 0          0       20            10     TRUE
#> 3 High-priority arrival 0          1       11            10     TRUE
#>   replication
#> 1           1
#> 2           1
#> 3           1
#>                      name start_time end_time activity_time finished
#> 1  Low-priority arrival 1          2        2             0    FALSE
#> 2  Low-priority arrival 0          0       20            10     TRUE
#> 3 High-priority arrival 0          1       11            10     TRUE
#>   replication
#> 1           1
#> 2           1
#> 3           1
env %>% get_mon_resources
#>   time server queue system            resource replication
#> 1    0      1     0      1 Finite queue server           1
#> 2    1      1     1      2 Finite queue server           1
#> 3   11      1     0      1 Finite queue server           1
#> 4   20      0     0      0 Finite queue server           1
#>   time server queue system            resource replication
#> 1    0      1     0      1 Finite queue server           1
#> 2    1      1     1      2 Finite queue server           1
#> 3   11      1     0      1 Finite queue server           1
#> 4   20      0     0      0 Finite queue server           1

I guess any solution to this would imply some kind of FIFO/LIFO preemption policy on the queue, not necessarily the same as that on the server.

[Enchufa2]

This behaviour is deliberate. Think about an emergency service where some patients are being attended, and the waiting room is full. Then, an extremely urgent case arrives and several patients need to be preempted. You simply cannot throw out anybody.

We can discuss the convenience of a new option to avoid exceeding the maximum capacity and how to implement it (should we reject the preempted ones or those waiting in queue?), but first we need use cases.

[nacnudus]

I think your hospital example is a good case for explicitly modelling the queueing space required to accommodate preempted patients, rather than hiding it in the background, but a more concrete example is routing phone calls through the exchange during high demand (e.g. national emergency), when urgent calls must cause other calls to be dropped altogether -- electronics can't be compressed to accommodate more calls in a finite space!

[Enchufa2]

As for the hospital example, your metric should be the percentage of time in which the total capacity exceeds certain threshold. So you are not hiding anything, but making it explicit!

As for the phone call service, it seems a reasonable use case. But I'm not sure whether there is preemption (or even priorities) in such a case... I mean, if the system is saturated, you have no circuits available, nor for normal calls nor for urgent ones.

[nacnudus]

I think this might be touching on similar matters to the reneging issue. The seize step is handling two events, entry to the queue and entry to the server, which makes preemption and reneging difficult to express.

You're correct that, if the system is saturated, you have no circuits available even for urgent calls, but a high-priority arrival could be allowed preemption into the queue just as they are allowed preemption into the server. It would mean ejecting a lower-priority arrival from the queue, just as they can be ejected from the server. In the telephone exchange example, that would mean dropping someone's call and playing them the dial tone.

[Enchufa2]

The seize step is handling two events, entry to the queue and entry to the server

That's not correct according to simmer's architecture. Queue and server are integral parts of a resource, and seize handles only one event: the entry to the resource. If it's successful, the resource manages the arrival, putting it either in the queue or in the server. If it's not, it means that the resource is full (server + queue, if exists), and the arrival is rejected. An ifseize would cover that cases in which you want to do something else if the seize fails.

a high-priority arrival could be allowed preemption into the queue just as they are allowed preemption into the server.

Again, we are starting from different definitions. For me (and in the literature about simulation in general I think), preemption refers to postpone a task already being served. A queue may have priorities (in fact, all queues are priority queues in simmer), but that's not preemption. SimPy adopts the same nomenclature, since you have priority customers with and without preemption.

Following the discussion above, the telephone exchange case is the typical example in which there is no queue. In fact, it is modelled traditionally as an M/M/c/c system (Erlang-B and all that stuff). So there are calls being served or no calls at all. And, if the system is saturated, there is no circuits available to even start a new call.

Don't get me wrong: I see the point of avoid exceeding the maximum capacity. But I need clear use cases, because preemption is hard, and I don't want to waste my time in something never used, you know... 😉

Moreover, if you perform a quick search, you only got simulators that don't drop preempted customers. Here one example, another and another.

[Enchufa2]

I've taken a look at this issue and I think it should be more or less easy to implement this option to keep the queue size limit. But I have to pick a good name for it. For instance:

add_resource("name", capacity=1, queue_size=1, preemptive=TRUE, queue_hard_limit=TRUE)

More ideas are welcome.

[nacnudus]

Looks good to me. Maybe queue_size_strict = TRUE would be more intuitive, as it's associated with queue_size.

What is the implementation? To drop pre-empted arrivals, or not to serve priority arrivals until there is room in the queue?

[Enchufa2]

+1 for queue_size_strict.

The preempted arrival is inserted in the normal queue, which handles the situation. So it may be rejected, or maybe another one with lower priority.