Algorithm to find the correct combination in a fast manner

Question

Assume I have 4 lists: jobs, workers, mechanisms and mechanism equipment.

• Currently I am firstly looping through jobs, lets call this the jobLoop.
• Inside jobLoop I'm looping through workerLoop, checking if worker is available and has required competences to do the job.
• If worker is OK, I'm looping through mechanismLoop, checking if worker can use the mechanism and if the mechanism is available. If no mechanisms are available, I fall back to workerLoop, looking for another correct worker.
• If mechanism is OK, I loop through mechEquipmentLoop, checking checking if worker can use the equipment and if the equipment is available. If no equipment is available, I fall back to mechanismLoop, looking for another correct mechanism.
• If mechanism equipment is finally okay, the algorithm is done. If not, the algorithm says items cannot be matched.

This is a simplified version, on each step there are many checks like if worker is allowed on the object where the job is done and so on.

I'm trying to think of a more efficient way to do this. Currently the time complexity for this algorithm should be roughly O(n^4), right? I'm not looking for code, just guidance on how to perform this.

Answer 1

IMHO - this algorithm is O(jwm*e) instead of O(n^4). j = number of jobs, w = number of workers, m= number of mechanisms, e = number of mech equipment.

If these lists don't change & if the answer is needed only once this is the best algorithm to execute. You need to visit all the inputs once at least.

Suppose these lists change and the same algo needs to execute for a given job multiple times you can do this.

Store the list of workers in BST (or a self-balanced tree-like AVL) with job competency as key. Suppose if there are multiple competencies for a worker then his data will be in all the competencies. The creation of the tree is O(wlogw) here w is the number of unique competency & worker combinations, not workers number alone. Deletion, Addition & Search will be O(logw). Here are we are assuming that competency - worker distribution is decent. Suppose if all workers have only one competency this will become O(w) once again.

The same applies to mechanism and equipment. This will make the search at every level to O(logm) and O(loge).

So for every job best case scenario of allocation is O(logw * logm * loge), with a overhead of O(wlogw + mlogm + eloge). For all jobs it will be (j * logw * logm * loge).