diff --git a/swh/scheduler/celery_backend/config.py b/swh/scheduler/celery_backend/config.py
--- a/swh/scheduler/celery_backend/config.py
+++ b/swh/scheduler/celery_backend/config.py
@@ -230,7 +230,12 @@
 
 def get_available_slots(app, queue_name: str, max_length: Optional[int]):
     """Get the number of tasks that can be sent to `queue_name`, when
-    the queue is limited to `max_length`."""
+    the queue is limited to `max_length`.
+
+    Returns:
+        The number of available slots in the queue. That result should be positive.
+
+    """
 
     if not max_length:
         return MAX_NUM_TASKS
@@ -238,7 +243,7 @@
     try:
         queue_length = get_queue_length(app, queue_name)
         # Clamp the return value to MAX_NUM_TASKS
-        max_val = min(max_length - queue_length, MAX_NUM_TASKS)
+        max_val = max(0, min(max_length - queue_length, MAX_NUM_TASKS))
     except (ValueError, TypeError):
         # Unknown queue length, just schedule all the tasks
         max_val = MAX_NUM_TASKS
diff --git a/swh/scheduler/tests/test_config.py b/swh/scheduler/tests/test_config.py
--- a/swh/scheduler/tests/test_config.py
+++ b/swh/scheduler/tests/test_config.py
@@ -45,6 +45,16 @@
     assert mock.called
 
 
+def test_get_available_slots_no_more_slots(mocker):
+    mock = mocker.patch("swh.scheduler.celery_backend.config.get_queue_length")
+    max_length = 100
+    queue_length = 9000
+    mock.return_value = queue_length
+    actual_num = get_available_slots(app, "anything", max_length)
+    assert actual_num == 0
+    assert mock.called
+
+
 def test_get_available_slots(mocker):
     mock = mocker.patch("swh.scheduler.celery_backend.config.get_queue_length")
     max_length = 100