|
Hi all,
I'm hoping someone can help me out with an algorithm question I got stuck on, while contemplating optimal scheduling algorithms (as one does lol).
Consider a basic task scheduling system, where there's a queue of "Tasks" that need to get done, a pool of "Workers" that can execute work (one at a time), and a scheduler that pulls work form the queue and assigns to the workers in some fashion.
( [Task1] [Task2] [Task3] ... [TaskT] ) ---> [Scheduler] ===> ( [Worker1] [Worker2] ... [WorkerN] )
I've been thinking about various optimal scheduling algorithms for such a system, with various parameters.
For this discussion, let's assume:
- The work is uniform (all Task units are exactly the same).
- "Optimal Scheduling" just means "If I add a bunch of work to the queue, all of it will be completed ASAP."
The Trivial Case
If, in addition to tasks being uniform, all workers are perfectly uniform, it's easy to see that assigning the work to the first available free worker is optimal, and that the scheduler can just be a dumb round-robin allocator of work.
The Heterogeneous Worker Case
Suppose we have an added constraint: Not all workers are the same; they take different amounts of time to perform a work unit. Maybe they run on a heterogeneous fleet, and some are on better hardware....
In that case, if we want optimal scheduling, we can do so greedily, by always assigning to the worker that will become available the soonest given one more unit of work (i.e. "store workers in a priority queue sorted by 'when it will be done with all its work, given one more unit of work'")
The Heterogeneous Worker with Scheduled Work Case
Ok, THIS is the one I am stuck on.
Suppose, in addition to the workers being different, we ALSO have a constraint where each unit of work becomes available at a specific time t into the execution.
The aforementioned greedy approach won't work anymore. Consider this example:
Workers:
- W1 takes 8 minutes to finish a work item.
- W2 takes 10 minutes to finish a work item.
Work:
- Task1 is available immediately (t = 0)
- Task2 is available one minute in (t = 1)
With the greedy algorithm: T1 will be assigned to W1, and T2 will be assiged to W2 one minute in, resulting in all work completing after 11 minutes.
However, the optimal solution is, T1 gets assigned to W2, and T2 gets assigned to W1, making T1 the long pole, and allowing the work to complete in only 10 minutes.
Intuitively, it kind of feels like this has to become a search/backtracking problem, perhaps with heavy pruning of nonsensical choices, but... is there a simpler solution I'm missing? I keep getting the sense that there's a viable DP approach, if we're generous with things like declaring all times are integers, and throwing everything at the slowest worker is guaranteed to take less than some reasonably small amount of time...
... or maybe there IS a greedy solution, and I'm just not seeing it...
Any thoughts/direction here?
|
|
|
|
|
|
Thanks for your response!
Sorry if I wasn't clear; in that last example, we do know exactly how long a specific worker would take to finish any task (the tasks are all the same, and it's just based on the efficiency of the worker). It's a totally contrived example. 
|
|
|
|
|
Trying to (automatically) schedule based on an "individual's performance levels" is "insane".
"Capacity" (planning) is based on history for a particular "type of resource": e.g. Senior Analyst "hours"; etc.
If a "resource" is not performing, you "demote" them and assign them to a different "resource group", instead of trying to factor in "individual" performance factors.
One estimates based on x hours of resource (type) A and resource type B, etc.
Not 10 hours of "Sally" OR 12 hours of "Bob", if "Sally is not available".
It's 10 hours of "Junior Programmer" time (or whatever), so if "Bob" leaves, you're not looking for another Bob.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
I'm creating a chess engine and I've tried to implement futility pruning. Results are sometimes worse than without it. Could somebody tell me what I'm doing wrong? My margin is set on 601 (pawn is set 200, knight/bishop 600 for example) Thanks
Same position
without futility on depth 5
Score: 90
Nodes: 89383
Depth: 5
Time: 2011ms
with futility on depth 5
Score: 90
Nodes: 85808
Depth: 5
Time: 1867ms
without futility on depth 6
Score: -16
Nodes: 836935
Depth: 6
Time: 12360ms
with futility on depth 6
Score: 65
Nodes: 855792
Depth: 6
Time: 12544ms
<pre>private int negamax(Position node, int depth, int alpha, int beta, int color, byte castling) {
if(depth == 0) {
return quiescenceSearch(node, alpha, beta, color);
}
if(depth == 1) {
int staticEval = color * countScore(node.pieces, depth, node.prevI, node.i);
if(staticEval + margin < alpha) {
return staticEval;
}
}
ArrayList<Move> possibleMoves = generateMove(node.pieces, node.prevI, node.i, getMoveByColor(color), castling);
if(possibleMoves.size() == 0) {
return color * countScore(node.pieces, depth, node.prevI, node.i);
}
orderMoves(possibleMoves, node.pieces);
int value = MIN;
for (Move possibleMove : possibleMoves) {
Piece tempPiece = node.pieces[possibleMove.getI()];
int prevPiece = node.pieces[possibleMove.getPrevI()].getType();
node.pieces[possibleMove.getPrevI()].move(possibleMove.getI(), possibleMove.getPrevI(), node.pieces, 0);
byte tempCastling = setCastling(node.prevI, node.i, castling);
Move temp = new Move(node.i, node.prevI);
node.prevI = possibleMove.getPrevI();
node.i = possibleMove.getI();
int tempValue;
tempValue = -negamax(node, depth - 1, -beta, -alpha, -color, tempCastling);
value = Math.max(value, tempValue);
undo(possibleMove.getI(), possibleMove.getPrevI(), node.pieces, tempPiece, prevPiece);
node.prevI = temp.getPrevI();
node.i = temp.getI();
alpha = Math.max(alpha, value);
if (depth == searchDepth) {
if (value > bestMoveValue) {
bestMoveValue = value;
bestMove = new Move(possibleMove.getI(), possibleMove.getPrevI());
}
}
}
return value;
}
|
|
|
|
|
My teacher seriously glossed over finding values of c and n0 for big O and big Omega.
For big Omega he said add coefficients and if there's a negative, flip the value.
Now I have a question asking me to prove 7n-2 is Ωn
By his explanation, c = 1/9
Which would give me (1/9)n <= 7n-2
Which seems unnecessary since c and n0 could be 1 and it would still hold that cn is <= 7n-2
Any thoughts, comments, helpful suggestions?
|
|
|
|
|
I am finishing up a course and it got me thinking about algo design. There were 21 people in our group for a 4 week course. Each week, we were split into 5 separate groups. Ideally, you would never have anyone in the same group with anyone that they were in a group with previously. In actuality, this was poorly executed. For instance, I was in a group with Sally from London in 3 of the 4 weeks.
I was thinking to create an algo for them next time so they don't have the problem. When I got to thinking about it I could only think to do it by brute force. Essentially, loop through each person until groups were made with minimal repetition. This would work when dealing with a group of 21, needing 5 subgroups of 4 or 5, 4 times. However, this would become unmanageable if the group was 100 times the size.
So the question is, starting with a group of size X, how do you divide it into Y groups, Z times, with the goal of minimizing overlap.
I imagine this is a simple problem using high school level combinatorics, but I can't seem to get started.
|
|
|
|
|
This kind of problem is treated in the mathematical discipline called Block design - Wikipedia[^] .
Unfortunately it is more than 30 years ago I had some lectures on this topic at university, so I can't remember any actaul algorithm. But maybe you can start searching for algorithms in this category.
I dimly remember that there are algorithms for finding specific designs that are better than brute force, by recombining solutions from a smaller scaled problem into solutions for a larger problem. but I'm not sure that would work for this problem.
Good luck!
P.S.: assuming you're not a student of mathematics, I suggest you try the idea I described, i. e. scaling up the problem incrementally. E. g. you solve the problem for a group of size Y (trivial), then you increase the group size one by one and solve the problem for that size, based on the previous results. Then you keep increasing the group and finding the best solutions for the new size.
To get a new best distribution at any step, use the best distribution(s) from the previous step, and test all valid options for adding the new group member. Then decide which one(s) cause the least overlap and proceed.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
modified 8-Aug-18 7:59am.
|
|
|
|
|
Your end goal is a "list" of "groups"; therefore, your only recourse is "brute force".
What an "algo" gives you is "the number of combinations for x taken n at a time"; i.e. a "number".
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Gerry Schmitz wrote: Your end goal is a "list" of "groups"; therefore, your only recourse is "brute force".
I beg to disagree. See my answer above. The mathematical discipline of block designs deals with such problems and algorithms to approach them. The discipline wouldn't exist if it weren't possible to solve these problems without resorting to brute force.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
|
|
|
|
|
I consider anything that has to be "iterated" as "brute force".
Sorry, but your "answer" was a non-answer: Quote: ... can't remember any actaul algorithm .... I'm not sure that would work for this problem ...
I "can" come up with a "routine" to produce the list in question.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Gerry Schmitz wrote: I consider anything that has to be "iterated" as "brute force".
Then we have a different understanding of brute force. In my book, brute force means testing all possible solutions. The number of possible group subdivisions for a group of size N is exponential in N. The effort of solving a combinatorial problem by brute force is (believed to be - see link below) exponential. Whereas the algorithm I described above is polynomial.
If you believe that is the same, then that is equivalent to saying P=NP[^].
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
|
|
|
|
|
You are right that this is a way too crude way to look at this from a mathematical view. Integration is a good example, as brute force summation can be done, but does not always give the correct answer, so Runge Kutta methods are (usually) used instead on non-stiff problems.
|
|
|
|
|
If you actually looked at the problem requirements, you would see that the "state" at stages 0 and 1 are clearly defined; and very limited (no "joins"; then 4,4,4,4,5 in any combination).
As since the previous "state" is recursively fed to the next stage in order to set the context for that stage, it should be obvious that the number of "unique" combos rapidly dwindles to 0; and you are simply now trying the "minimize" the objective function ("discord") for the remaining "time-limited" horizon (i.e. "classes").
Classic dynamic programming recursion.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
What you have is a "scheduling problem".
It is an example of "dynamic programming".
Dynamic programming does not supply a "one size fits all"; it generally has to be tailored to the "problem".
And in general, dynamic programming is reserved for those situations where "linear" methods are not suitable.
This is one of those cases; like quantum computing, "exclusivity" was recently upended by an 18 year old who showed "classical computing" is still in competition with quantum computing.
Op wanted a "solution", not just theory.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
While I don't think there is any 'scheduling' involved (no time constraints, order of group subdivisions irrelevant), I agree that it is a problem that needs a tailored solution. I suggested a recursion over total group size, you suggested a recursion over the required number of group distributions. I think both concepts are equally suitable, and both will need to be tuned to the problem to turn them into workable solutions.
I see you are using terms from computer science, whereas I am using mathematical concepts. That doesn't mean the ideas they represent are so much different, or incompatible. It's more like one of us is discussing the optimal temperature wheras the other insists on a specific color - we're not disagreeing as far as I can see 
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
|
|
|
|
|
Member 13939652 wrote: but I can't seem to get started.
Start by solving a subproblem by hand with a sheey of paper and a dew colored pencils.
First draw a table of peoples (21x21), then build a solution as long as there is no overlap.
Use a different color by turn (week).
in the table, fill cells where every pair of people are in same group the same week. Go as far as you can without overlap.
The way you did it is the base of your algorithm. Then when you deal with overlap, see how to minimize the number of people that were in sale group the same week.
In a group of 5, each member is pairing with 4 other people.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
modified 1-Sep-18 23:16pm.
|
|
|
|
|
I'm aware this is a lazy question 
All my hope are in you: @Stefan63
Is there a guide how to prevent from ending a "Simplex Downhill" to end in a local Minimum?
Sorry and thanks for any hint.
It does not solve my Problem, but it answers my question
modified 19-Jan-21 21:04pm.
|
|
|
|
|
Hello.
In general, there is no way to prevent ending up in a local minimum.
However, in some special cases it may be possible. E. g. if you want to find the minima of a polynomial function, you can instead search for the roots of its derivative, and use Sturm's theorem - Wikipedia[^] to enumerate and localize every single root.
Otherwise there are some methods that can increase the chance of homing in on the global minimum. You can use Simulated annealing - Wikipedia[^] to prevent getting stuck in a local minimum: basically this algorithms shakes up the current best solution to give it a chance getting out of a minimum. The chance of doing so is smaller for better solutions, therefore the hope is to end up in the best one - the global minimum. Also, the chance of switching to another (local) minimum is decreased over time to ensure that the algorithm comes to an end.
Or you could use a Genetic algorithm - Wikipedia[^] to find a solution that is pretty much guaranteed to be at least close to the global minimum. Basically this is a guided trial-and-error search algorithm which can be programmed to always keep the current best solution(s). This algorithm is more suitable for discrete or combinatorial problems. But it can also be applied to continuous problems.
If you can tell me more about the specific kind of problem, I may be able to offer better advice.
P.S.: I didn't realize that "Simplex Downhill" may refer to a specific algorithm. The term 'Downhill' by itself is often used in conjunction with many minimization algorithms. But did you mean this[^] ? If so, the above suggestions are of course of little help, unless you are looking for ways to modify that algorithm using ideas from other minimization techniques. E. g. the basic concept of Simulated Annealing is to allow steps of arbitrary size with a low likelyhood for very large steps. You could use that idea by allowing new points to be constructed relatively far away, potentially nearer to another local minimum.
Unfortunately I have no experience with the Nelder-Mead method myself.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
modified 6-Aug-18 9:39am.
|
|
|
|
|
Wow! First of all thank you _very very much_ for your time and your great answer. I Need some time to go through all this, especially "Simulated Annealing" which I do not know until now.
Quote: But did you mean this
Yes exactly, I'm using Amoeba. But meanwhile (it looks like) I recognized, that I'm on the wrong path (not completely sure about it).
Basically I Need to solve a more or less easy Thing:
t= w * b + A * c
where
t is a vector (400 items)
w is a scalar
b is a vector (400 items)
A is a 400x4 matrice (4 can be 1...8)
c is a vector (4 items, 1...8)
t is the target, b is the current Situation (captured by a measurement). The question is: what are the optimal w and c to come from b to t while w should not differ too much from 1 (1-w as small as possible and w <= 1) and c should be as small as possible and all items need to be >= 0. In other words: How much I Need to throw away from b and what I Need to add with c to bring b as good as possible to t. At the Moment "as good as possible" means best curve fit, but Needs later to be Extended by a completely non linear function (spectroscopy analysis), that's why the simplex approach.
All this sounds so easy, but the Problem is: Sometimes (when the math model fits the physics well), b is a linear combination of A and that is a Problem, that the simplex method usually Ends in a w=0...
Ok, using simplex here is most probably the wrong approach. Meanwhile I calculated this with "Singular-value decomposition" of A.The results are great, but I'm afraid I choose too much nice test data. With SVD I calculate a scan for different w's: t-w*b= A*c. At the Moment I don't trust the results because I always get c vector with positive items. This would be great, because this is the what I need, but for me it Looks more like a mistake from my side. Why I should be that lucky to get always positive c values...
Sorry to text you that much.
Bruno
It does not solve my Problem, but it answers my question
modified 19-Jan-21 21:04pm.
|
|
|
|
|
Hello again
I'll try to reformulate your problem in a more formal way.
First, you have an expression with 5 unknowns (w and the 4 components of c: c1, c2, c3 and c4). By your description, everything else are known values. In other words you have a function of 5 variables
f(w,c1,c2,c3,c4) = w*b+A*c
Next, you want this expression to come as close as possible to a target vector t. You can express this by defining a new function g that computes the difference between f(w,c) and t:
g(w, c) = w*b + A*c - t
And you want the resulting vector to be as small as possible:
norm(g(w0, c0)) = Minimum(norm(g(w, c))) for any w in [0,1] and any ci in [0,infinity]
Since this is a linear problem, none of the algorithms I previously suggested will be preferable. If you use the Euclidian norm, you can minimize the square of the norm instead, to avoid the square root, and turn the function into a quadratic function. That means there is only one minimum, and you don't need to care about getting stuck in local minima.
A quick search also found me this algorithm which I wasn't aware of before: Benson's algorithm - Wikipedia[^] . Maybe this will help.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
|
|
|
|
|
Dear Stefan
Thank you very much again. I will makes some tests based on your Input.
Thanks again.
Regards
Bruno
It does not solve my Problem, but it answers my question
modified 19-Jan-21 21:04pm.
|
|
|
|
|
Building on my previous explanations, I realized that the solution may in fact be rather easy to find. the only possible complication is that the global minimum may not lie within the required ranges for w and c. In that case the solution would lie somewhere on the boundary of the parameter space.
The algorithm will work like this: since you want to find the minimum for the norm of the function g, an equivalent task would be to find the minimum for the squared norm of g! Therefore the target function to minimize is:
h(w,c) = square(norm(g(w,c))) = g(w,c)*g(w,c) = (w*b + A*c - t)*(w*b + A*c - t)
A necessary condition for the minimum is that all partial derivatives are 0:
dh/dw = dh/dc1 = dh/dc2 = dh/dc3 = dh/dc4 = 0
This gets you:
dh/dw = 2*(w*b + A*c - t)*b = 0
dh/dci = 2*(w*b + A*c - t)*Ai = 0 , where Ai is the i'th column of A, and i = 1, 2, 3, or 4
These are five linear equations in w, c1, c2, c3, and c4, that can be solved easily with a linear equation solver.
Once you have the solution to this LES, you will have to verify that the solution is actually a minimum and not a maximum, and that the constraints for the parameters are fulfilled. If this is not the case, the solution must be at the boundary of the constrained parameter space, i. e. one or more of the parameters must be fixed at a limit of their valid range. This means you can only use the linear equations above for the partial derivatives of the other variables, leaving you with a LES of 4 or less variables that can also be solved easily.
The only problem here is the complexity of searching each part of the boundary: if there were three restricted parameters, and the restricted range would describe a 3d cube, you'd have to search each of the sides, and each of the edges, and each of the corners of the parameter cube for a local minimum, and then you'd have to compare all minima you've found to find the global minimum. Since you have 5 variables, it gets a lot more complex than that...
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
|
|
|
|
|
I tested (I am testing, not yet sure all is bug free) and at the moment I face the problem in case b can be expressed very well by A. As expected w does go then down near zero. But I need to test more.
Thank you for your big inputs, it opened my mind for new approaches.
It does not solve my Problem, but it answers my question
modified 19-Jan-21 21:04pm.
|
|
|
|
|
If b is a linear combination of the matrix columns Ai, then you can choose w to be equal to 1, without constraining the solution space.
If it only comes close, it gets tricky: in that case a standard algorithm for solving the LES I described - e. g. Gauss Elimination - may run into numerical problems due to cumulated rounding effects. A simple method to minimize such numerical issues is to rearrange the LES with a Pivot Search. There are more advanced and stable methods, but for a system with just 5 equations Pivot Search should work just fine.
The Gaussian elimination - Wikipedia[^] entry shows pseudo code for Gauss Elimination with Pivot Search at the end.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
