Queue Based (Best) Scheduler

r_2017_2

#1

How it works

A group of robots will process multiple queues/processes, one item at a time, within a specific environment

  • processes will not work in a get item loop anymore (one item at a time)
  • which means that robots within an environment will have access to multiple queues/processes.
  • items will be taken out based on due date, priority, queue position
  • you can still schedule (process this queue between 12:00 and 14:00)

Why

  • it gives maximum robot utilization
  • you don’t need to figure out complicated schedules anymore
  • we don’t need to figure out the robot load balancer feature (i have many items in this queue therefore bring in more robots here)
  • client workflows are simpler (no looping) - still initialize app/verify you’re in the right place should be done

Issues

  • queue (and assets) per process need to be implemented first (which is a good thing)
  • all you need to do is to set the right priorities on those queue items
  • the server should figure out not to change the process too often for a specific robot - otherwise he’ll need to run init sequences all the time - this will be difficult
  • option to pause a queue

Rate it:

  • Extremly Important
  • Very Important
  • Important
  • Slightly Important
  • Not Set

0 voters


Scheduling Opinion
Automatically run bots on new queue item
End schedule after Queue is empty
#2

Hi Mihai,

As discussed on our call earlier I do agree that we need to improve automated scheduling but I have some concerns:

  1. What happens to existing processes that do not currently use a single queue?
  2. How would each process know what “state” the machines are in prior to starting the next item. This would require a fair amount of logic that would need amending every time a new process was developed.
  3. What happens when a particular process needs to be stopped for some reason? e.g. don’t run this process today.
  4. If a VM is deliberately being denied access to a certain account would this be handled by available environments?

A suggested alternative approach to this problem is as follows:

Persist with multiple tables but have an optional view to drive the robot process rather than a single queue. This view would be driven by a configuration page (possibly attached to the scheduler) allowing administrators to increase/decrease prioritization of queues rather than queue items, schedule start/stop times or max/min number of cases to work. Additionally a particular queue could be temporarily disabled if there were an issue with it.

The optional use of this would mean that existing processes would not need to be amended and the configuration tool would mean that worfklows do not have to deal with multiple scenarios. For example, if you were running process 1, then 2 then 1 then 3 then 1 you would have to continuously check for applications, close applications open new applications which ultimately would be less efficient.

What are your thoughts?

Richard


#3

A simple approach with less impact on an existing setup would be:

  • Have a free floating robots Environment (let’s say Freelancers)
  • Build a (cron) job in Orchestrator that starts and stops freelancer robots automatically
  • Projects must use ShouldStop activity to make robots responsive to the stop signal

How this job works:

  • Check if there is a Freelancers environment. No freelancers, no balancing, no headache.
  • Calculate if there are queues needing extra workforce by queue priority, number of items, average processing time, number of robots on the job, any items deadline
  • Count freelancers on less important jobs
  • If not enough freelancers to satisfy all demands, raise a warning/notification in Orchestrator
  • Send Stop signal to any recalling freelancers. It may take a while until they finish their current assignments.
  • Dispatch any available freelancers between jobs according to priorities
  • Reschedule cron

#4

@extremihai
We’ve had similar discussions in the past about cross-queue prioritization.

It all boiled down to how exactly the algorithm would look like (buffer size, prioritization options, batching of items before process switch etc.) and to what extent it would be customizable, especially making sure changing processes doesn’t eat up too much time.

Sidenote/opinion - doing it as a cron, while nice to some, will up a barrier of entry to who can change it (not that it’s too hard, just different and we’re constantly switching languages anyway when working with robots). It does also sound more like a “hack” than a fully integrated feature, which could limit maintenance visibility of what is actually happening.

Bearing that in mind, one thing to note is also how the configuration (and licensing) for these would be handled. In 2016.2 there’s already a limitation that to run a robot (any robot, even from studio), you need to have it registered, which leads to a conclusion that if we’re having 10 processes, 1 user account per process (probably would need more) deployed on 5 machines… that’s 50 registered robots?

In conclusion - I’m all for robot flexibility (we actually have some that have built-in “internal queueing”), but visibility - in setup, maintenance and licensing - should be key, otherwise it’s a nightmare waiting to come to fruition.

Regards,
Andrzej


#5

Since the first proposal requires many changes here’s a simplified solution. @Cosmin_Ion_Nicolae

At this stage they are quick proposals and will be refined.

Solution 1
Step 1. Link processes with queues
P1 - Q1
P2 - Q2
P3 - Q3

Step 2. Assign priorities to queues based on the number of items
Q1 - [1 - 9] - 2
Q2 - [1 - 9] - 3
Q3 - [1 - 29] - 4
Q1 - [10 - 99] - 11
Q2 - [10 - 49] - 12
Q3 - [30 - 149] - 13
Q1 - [100 - ] - 23
Q2 - [50 - ] - 26
Q3 - [150 - ] - 20

where[n1 - n2] is the min number - max number of items in queue and the last number is a priority manually assigned per interval.

Step 3. Every x minutes an algorithm will poll the server and based on the number of items in each queue will stop/start processes.

Let’s say that we have 73 Q2 items, 80 Q3 items and 80 Q1 items therefore
PriQ1 = 11, PriQ2 = 26, PriQ1 = 13

P1 will be scheduled to run as it has the highest Pri number.


Solution 2
Assign a polynomial formula to calculate priorities (…and - to think about it - take into consideration the queue item prioritiy)
PriQ1 = n1*n1 + 10
PriQ2 = 3*n2 + 100
PriQ3 = n3 + 200


Solution 3
These processes will run against the same environment and it contains n robots.
Divide the robots within the environment proportionally according to the previous calculated score.


#6

@badita
Well for now the simplest solution I think is to just assign priorities based on the number of items. This will enable us to keep item numbers in each queue at a manageable level. The only thing I would like to add is to integrate the number of robots that are currently running a process into the equation. So it can be something like:

Q1 = 11, Q2=26, Q3 = 13

but then we integrate the current number of robots that are running that process so:
PriQ = Q - n*f, Where:
Q is the priority of the queue
n number of robots that are currently running the process
f constant that will dictate the role of number of robots.

Using a polynomial solution although more complex is also pretty good and will allow for more possibilities in the future. The same as before I would integrate the number of robots currently running that process in that calculation too.

Finally we will run the process that has the highest priority but as a future improvement I would suggest to split the scheduler into two separate systems. One that deals with priorities which at the end of calculation should return the optimal ratio for the robots, for example:
P1 - 50 %, P2 - 15%, P3 - 35%
And a different system that judges which of the processes to start to maintain this expected ratio.

The problem of course can be that if you have a lot of items in a queue it can quickly lead to scenarios in which only one of the processes is actually running.

In the future might be a good idea to remove the concept of priorities from the user and allow to specify metric as “I need that many items from this queue to be processed in a day” and “I want these two processes to be linked”.

An interesting mechanism might be also to be able to graphically define rise and cutoff item numbers through a polynomial function as if an queue has a low number of items it doesn’t need that high of a priority and also after a certain level priority should not increase more with the number of items.


#7

My take on this.

First we should define what we’re trying to achieve, which is to minimize the processing time for a group of processes, robots and queues. That means that all queues should finish processing at the same time.

For that, the number of items in a queue, on its own, is not enough for a queue-balancer. A queue with 100 items could overall process faster than another Q with 10 items, and then you end up needing to help an automatic system that should be set-and-forget.

How it would work: we already know the average processing time per item, so we can pretty accurately estimate the total processing time for the current queue, and divided by the number of robots processing the queue, we get the actual required processing time.

  • RequiredTime(Q) = TotalQueueTime / # ofRobots

Although I advise against using queue Priorities, they can be included as simple multipliers in the above formula.

  • RequiredTime(Q) = TotalQueueTime / # ofRobots * Priority[1-3]

  • Then allocate a robot from the queue with the smallest requiredTime, to the one with the longest time.

  • Repeat.

In a few steps this would balance the queues to equal (and minimal) processing time.


This solution doesn’t take into account the use of the robots by “outsiders” (processes outside of the container/orchestration). For that, an alternative method can be used to estimate the RequiredTime(Q).

  • Orchestrator can average the time between successfully processed transactions for each queue, irrespective of the number of robots working on it.
    Of course, more robots per queue ==> shorter “processing time”, and that’s what we want. Because that will also take into account for the use of robot time by outsiders.
  • Add the Q priority and we get:
    RequiredTime(Q) = X items * AverageSuccessfullyProcessedInterval * Priority[1-3]

Then like before, allocate robots from the fastest to the slowest Q to ballance all processes in that group/orchestration.


#8

Hi Mihai,

This is a typical scheduling problem. We should also take a look at these papers which covers different scheduling algorithms including DAG’s (directed acyclic graph).
• For workloads without dependencies [http://www.softcomputing.net/nnw_hesam.pdf]:
o Min-min
o Max-min
o Longest Job to Fastest Resource - Shortest Job to Fastest Resource (LJFR-SJFR)
o Sufferage
o WorkQueue
• For workloads with dependencies [http://inspirehep.net/record/923687/files/cer-002642925.pdf]:
o Polynomial-time algorithm for tree-structured DAGs
o Scheduling of interval-ordered DAGs
o Sarkar’s algorithm
o HLFET - Highest Level First with Estimated Times
o ETF - Earliest Time First
o ISH - Insertion Scheduling Heuristic
o FLB - Fast Load Balancing
o CCF - Cluster Ready Children First
o DSC - Dominant Sequence Clustering
o CASS - Clustering and Scheduling System
o DCP - Dynamic Critical Path
o MCP - Modified Critical Path
o MD - Mobility Directed
o Hybrid Remapper
Also I think we should define a DAG (Directed acyclic graph) of workflows/queues which expresses the dependencies between workflows/queues.


#9

Load balancing can have many algorithms and ways to implement. This is my view. It is assumed the number of BOTS be correctly assessed before any Load Balancing algorithm to be effective

Multiple Queues to Multiple Robots assignment. Queues can be sequenced optionally incase of multiple High priority items available in multiple queues)

Define the priority of Queue Items (High, Medium, Low) - Only 3 priority levels should be sufficient

It is assumed that transaction volume is inversely proportional to the priority

Low Priority Items (Assign Dedicated 10-20% Robots)

Medium Priority Items (Assign Dedicated 20-30% Robots)

High Priority Items Multiple flags for processing by the remaining 50-70% Robots
FIFO by any assigned and available Robot
Sequening defined in the Queue to Robot assignment
Optional Schedule defined for any queue to be processed. During this schedule all the available Robots to process this queue)

At all times Robots to process items (any priority) based on FIFO rule. So if no High or Medium priority items exist then all the Robots should process Low Priority Items


#10

@Pankaj_Sharma @Stefan_Adam I am aware of this. I’m asking for a concrete algorithm proposal that

  • solves the customer pain
  • it is feasible to implement

I have proposed a polynomial based formula (based on the queue item number/priority)