Bin Packing? Queueing? Scheduling? Help!
Greg Rickford
My problem seems to have elements of Bin Packing / Queueing and Scheduling -
can anyone point me in the right direction for a solution? Its akin to an
inventory / shelf stacking situation
We have a number (n) of queues of car parking spaces, say 5 long, one behind
the other. Cars arrive at randon and are added at the back of the queues - on
a basis that I am trying to determine !
When position 5 (the back of the queue) is full in all queues, then no more
cars car park. Cars leave from the front of queues. Cars do not "shuffle up"
but only move when their time comes to depart. So when a queue is full (5
cars), the rearmost car prevents any more vehicles being added until it and the
4 cars in front have all left. Five spaces then become free.
The departure time for each car is known at the time of its arrival, the
question is how to allocate the new arrival to a particular queue to optimise
the use of parking spaces?
Obviously, one constraint is that a car cannot be added to a queue where the
one in front has a later departure time. Empirically, it seems to me, that
minimising the difference in departure time between the first and last vehicles
in any queue returns those five spaces into re-use most efficiently? But should
a new arrival be added to a part filled queue or be made the head of a new
queue?
Any help or guidance would be gratefully received as thsi is actaully a
practical problem and my math just can't cope :-) Many thanks.
Greg
_\\|//_
('0-0')
~~~~o00~(_)~00o~~~~ Wot! No spam? Great!
*** REMOVE THE ".NOT.NET" TO REPLY ****
Uffe Kousgaard
It seems like an interesting problem and it could be checked with simulation
what strategy is the best, but you haven't provided any information about
for how long time the cars stay in the queue. All the same time, does it
depend on something else or is it also random as the arrivals are?
"Greg Rickford" <gric...@aol.com.not.net> wrote in message
news:20011202102335...@mb-ct.aol.com...
Greg Rickford
>what strategy is the best, but you haven't provided any information about
>for how long time the cars stay in the queue. All the same time, does it
>depend on something else or is it also random as the arrivals are?
Uffe,
Thank you for your interest.
The time the cars stay at the car park (queue) is also random (probably a
normal distribution with some average duration that is not known at the
moment). I think that if we implement some (computerised) system, it could
monitor arrival and depart information to get a (moving) fix on the average
time cars stay and the variability (standard deviation)
Your further thoughts and comments would be welcomed. Thank you.
Uffe Kousgaard
I still think simulation is the best way to find a strategy. It may not have
to be that complicated.
Basically you want to avoid 2 situations:
1) All queues are filled and you have to reject a car.
2) There is only room in queues, where a car can not leave at the desired
time, but will have to wait for later.
The only "problem" is to decide, which strategies to test and then implement
them. The basic simulation is "quite" easy, I think.
HTH
Uffe Kousgaard
"Greg Rickford" <gric...@aol.com.not.net> wrote in message
news:20011202190032...@mb-fr.aol.com...
Lutz Tautenhahn
I have something for you to play around with. Look at the
JavaScript simulation at
www.tu-chemnitz.de/~luta/plt/queue.html
but you MUST come with IE 5.x or Netscape 6.x, otherwise it
will not work. If you want to use the script on your local machine,
you must also download the file diagram.js which is in the same
directory. I hope this simulation fits to your model. I didn't spend
too much time with the heuristic, so you can probably create a
better one. Good luck !
Lutz Tautenhahn
"Uffe Kousgaard" <uf...@routeware.dk> schrieb im Newsbeitrag
news:3c0c9b95$0$29611$edfa...@dspool01.news.tele.dk...
Uffe Kousgaard
Really nice graphics, but some explanation would be great. The 0.5, 1.5 and
2.5 on the Y-axis is quite confusing, if I have understood just some of it
correctly.
What does the grey and pink numbers mean at the top?
Does the colors on the figure have a meaning?
Regards
Uffe
"Lutz Tautenhahn" <lutz.ta...@wirtschaft.tu-chemnitz.de> wrote in
message news:9uk1f1$gd9$1...@narses.hrz.tu-chemnitz.de...
Lutz Tautenhahn
it seems I cannot hide, that I'm not a poet, but only a programmer.
The simulation at
www.tu-chemnitz.de/~luta/plt/queue.html
is updated now, with some explaination, as you wanted.
I also fixed a bug in the code. (Did you encounter the bug?)
Regards,
Lutz
"Uffe Kousgaard" <uf...@routeware.dk> schrieb im Newsbeitrag
news:3c0dd387$0$7878$edfa...@dspool01.news.tele.dk...
Greg Rickford
That looks really interestin!! I agree with you that it seems empirically that
minimising the difference between depart of car 1 and car 5 in a queue makes
best use of the spaces. The big question is at the end of your commentary of
the web page - how to decide whether to add to an existing queue, make a new
queue or turn them away! I cannot give this time until Friday but will be glad
to follow up on your great work so far.
Kind regards,
Greg
>From: "Lutz Tautenhahn" lutz.ta...@wirtschaft.tu-chemnitz.de
>Date: 12/5/2001 6:08 PM GMT Standard Time
>Message-id: <9ulni4$sc2$1...@narses.hrz.tu-chemnitz.de>
>
>Sorry,
>it seems I cannot hide, that I'm not a poet, but only a programmer.
>The simulation at
>www.tu-chemnitz.de/~luta/plt/queue.html
>is updated now, with some explaination, as you wanted.
>I also fixed a bug in the code. (Did you encounter the bug?)
>Regards,
>Lutz
>
_\\|//_
Uffe Kousgaard
It is much better now. The only thing you miss now is a normal distribution
for the car park time instead of the uniform distribution, you are using.
And possibly some more strategies to test.
I didn't find your bug.
It all looks nice, but it is probably not so efficient for testing different
strategies, once you have more information on the actual car park time
during the day. That can probably not be considered the same.
Regards
Uffe
"Lutz Tautenhahn" <lutz.ta...@wirtschaft.tu-chemnitz.de> wrote in
message news:9ulni4$sc2$1...@narses.hrz.tu-chemnitz.de...
Lutz Tautenhahn
the next step could be, to model this with real data.
That means the real number of queues, and the real distribution
of arrival and car park times (this must not be normal distribution,
for instance car park time>=0 can not be exactly normal distributed).
The best would be, not only to get the distribution, but the real
data from, lets say 1 week, and to simulate with the real data
instead of the generated random numbers.
Then you could design some heuristics and find out which heuristic
with which parameter combinations achieves the best result in the
simulation.
[Maybe it can also be done by a neuronal net instead of a heuristic.
Our problem reminds me a bit of the backgammon game, for which
a temporal difference method for neuronal network learning was
succesful implemented in a computer progam, which is now one of
the strongest in the world.]
Of course you can speed up the simulation by switching the graphics
off and doing a loop instead of the Timer() function or decreasing the
timer interval from 1 sec to 0.1 sec or so, and also by using a compiled
binary executable instead of a script.
In my point of view, the main advantage of the graphical representation is,
that it makes it possible to study a heuristic in detail (using the step
mode), especially for the further improvement (testing/debugging) of a
heuristic, which would be hard if you had only a list of numbers and your
intuition.
Regards,
Lutz
"Uffe Kousgaard" <uf...@routeware.dk> schrieb im Newsbeitrag
news:3c0e9876$0$25412$edfa...@dspool01.news.tele.dk...