Re: Unusual Problem

On Nov 13, 5:04 am, "desktop" <s...@xxxxxx> wrote:
## The schedule calculated by Hamming Distance
## 513 001000000001 1
## 68 000001000100 2
## 1040 010000010000 3
## 10 000000001010 4
## 20 000000010100 5
## 1032 010000001000 6
## 129 000010000001 7
## 2112 100001000000 8
## 1152 010010000000 9
## 6 000000000110 10
## 640 001010000000 11
## 9 000000001001 12
## 130 000010000010 13 But there should only be 12
different!
## 36 000000100100
## 18 000000010010
## 192 000011000000
## 1025 010000000001
## 384 000110000000
## 12 000000001100
## 257 000100000001
## 2052 100000000100
## 48 000000110000
## 768 001100000000
## 34 000000100010
## 2560 101000000000
## 258 000100000010
## 1056 010000100000
## 514 001000000010
## 1088 010001000000
## 2049 100000000001
## 1280 010100000000
## 516 001000000100
## 72 000001001000
## 132 000010000100
## 2304 100100000000
## 544 001000100000
## 264 000100001000
## 144 000010010000
## 260 000100000100
## 2176 100010000000
## 1536 011000000000
## 96 000001100000
## 272 000100010000
## 1026 010000000010
## 33 000000100001
## 80 000001010000
## 3 000000000011
## 2056 100000001000
## 5 000000000101
## 288 000100100000
## 2064 100000010000
## 40 000000101000
## 3072 110000000000
## 160 000010100000
## 320 000101000000
## 528 001000010000
## 66 000001000010
## 520 001000001000
## 65 000001000001
## 2080 100000100000
## 17 000000010001
## 576 001001000000
## 24 000000011000
## 2050 100000000010
## 136 000010001000
## 1028 010000000100

I don't understand the above numbers. There are more than 12 different
numbers even though there are only 12 persons.

Further it should also be pairs of two persons. Am I reading the data wrong?

Yes, there are 66 different rows, one for each
combination. Each number represents a PAIR of workers.
The combinations of 12 items taken 2 at a time is
equivalent to asking "how many binary numbers have
exactly two 1-bits?"

That's called a transform, converting your problem
into an equivalent system for which tools are available
and then converting it back once solved. That's a
standard technique.

Look at the first row.

513 001000000001

The numbers are the same, the first printed in
base 10 and the second in base 2. Note that every
number in the base two column has EXACTLY two 1's
(and if you check the unshuffled list, you'll see
every possible pattern is represented).

You read this by mapping the bit position of the 1's
(which represent who's actually working) to the worker
index:

001000000001
||||||||||||
|||||||||||+-worker 0 is working
||||||||||+--worker 1 is not working
|||||||||+---worker 2 is not working
||||||||+----worker 3 is not working
|||||||+-----worker 4 is not working
||||||+------worker 5 is not working
|||||+-------worker 6 is not working
||||+--------worker 7 is not working
|||+---------worker 8 is not working
||+----------worker 9 is working
|+-----------worker 10 is not working
+------------worker 11 is not working

So, a partial decoding gives

## 513 001000000001 workers: 0 & 9
## 68 000001000100 workers: 2 & 6
## 1040 010000010000 workers: 4 & 10
## 10 000000001010 workers: 1 & 3
## 20 000000010100 workers: 2 & 4
## 1032 010000001000 workers: 3 & 10
## 129 000010000001 workers: 0 & 7
## 2112 100001000000 workers: 6 & 11
## 1152 010010000000 workers: 7 & 10

The reson for doing this is because we have functions
for testing an manipulating binary numbers, so it is
sometimes to our advantage to convert problems to
equivalent binary systems.

In this case, the tool is called Hamming Distance.
It's the number of bit position differences between
two binary numbers. For this problem, all the binary
numbers have exactly two 1's, so the possible Hamming
distances are

0: two positions match, the numbers are identical
2: one position matches, two bits in different positions
4: no position matches, four bits in different positions

By construction, there are no duplicates, so HD=0
cannot occur. If HD=2, it means some worker is working
consecutive events. When HD=4, consecutive events always
involve 4 different workers.

The algorithm scans through the shuffled list skipping
any HD=2's until it locates an HD=4 and then adds it to
the schedule. If it makes it all the way through the list without
locating an HD=4, it has to settle for an HD=2.
This process repeats until all combinations are added to
the schedule. If you look through the schedule solution,
you'll that HD=4 for every adjacent pair of numbers.

If you took the numbers straight out of the combination
generator, worker 0 would never work two consecutive
events, but would work every other event 11 times.
The random shuffling helps break up this pattern while
the Hamming Distance algorithm still keeps workers
from working consecutive events.




.

Relevant Pages

  • Re: Nine day week - Project 2007
    ... Not a solution but just to mention an area where very harsh labour ... workers on drilling platforms work in a practically ... such a schedule would likely generate would seriously erode productivity. ...
    (microsoft.public.project)
  • Re: Resource overallocation problem
    ... our schedule is not so strict and I don't have to ... and varying the units by time to meet you resource absences is your only ... 300% for 3 workers or whatever numbers you have. ... MS Project MVP ...
    (microsoft.public.project)
  • Re: Kurt Angle Comments On Release From WWE
    ... Anyone else feel Vince is at least *partly* responsible for stuff like this ... He implements a schedule so grueling with his workers on the ...
    (rec.sport.pro-wrestling)
  • RE: Help - populate a schedule using start/finish times?
    ... day of various workers. ... Crude example: ... I would like to know if it is possible to use this to produce a schedule on ... a seperate sheet by hour of the day, ...
    (microsoft.public.excel)
Quantcast