Thread Subject: Finding a number in a row and creating a matrix with it

Assume the following, S_Seq contains 5 different schedules which will give the respective times in S.

S =[110;109;115;107;113]
numMachines = 2
numJobs = 8
R=5 %size of S
S_Seq{1,1}={[1 4 8 6];[7 3 5 2]}
S_Seq{2,1}={[4 1 8 6];[7 5 2 3]}
S_Seq{3,1}={[3 7 8 6];[4 5 2 1]}
S_Seq{4,1}={[8 6 2 5];[7 3 1 4]}
S_Seq{5,1}={[1 5 3 6];[7 8 4 2]}

So, S(1)=110 is given by the sequence of jobs scheduled in machine 1, 1-4-8-6 and the sequence of jobs scheduled in machine 2, 7-3-5-2. And same thing with the others, so first row in S_Seq{x,1} is schedule for machine 1, and second row is for machine 2.

Now what I want to do is find for example how many times is job 1 scheduled in machine 1 in the 5 schedules, as it can be seen it is scheduled in machine 1 in schedule 1,2 and 5. Then I want to create a matrix Ejk of dimensions (numJobs x numMachines) where for example in the position (1,1), job 1 at machine 1 it will have the sum of 1 over the time where it is present divided by the sum of 1 over every number in S. So position (1,1) will be, (1/110+1/109+1/113)/(1/110+1/109+1/115+1/107+1/113). and so on for every position. If it is not present in any schedule then assign a 0.

I have coded this the following way but I am hoping someone can help me make this code faster.

Ejk = zeros(numJobs, numMachines);
E_B = sum(1./S);

for k = 1:numMachines
    for j = 1:numJobs
        Ejk_T = 0;
        for s = 1:R
            if S(s) ~= Inf
                Ejk_C = ismember(j,S_Seq{s,1}{k,1});
                if Ejk_C == 1
                    Ejk_T = Ejk_T + (1/S(s));
                end
            end
        end
        Ejk(j,k) = Ejk_T/E_B;
    end
end


Thanks in advance!!

I am going to present a method which will work on a matrix, rather than the cell array you have specified.
Let A = [1 4 8 6 7 3 5 2;
             4 1 8 6 7 5 2 3;
                 ....]

then
% find indices of 1:8 in each row (assumes that each row is a permutation)
[B,B] = sort(A,2);
% convert to logical matrix for jobs in machine 1
B = B<5;
% weights of the set
W = 1./S;
M = sum(W);
% Put the following line into an appropriate loop
E(1,1) = sum(W(B(:,1)))/M;

Note that job i is either treated by machine 1 OR machine 2 so
E(i,2) = 1 - E(i,1);

The above -pseudo- code is completely untested but should be quick. Surely a bsxfun guru can improve further still.

I am going to present a method which will work on a matrix, rather than the cell array you have specified.
Let A = [1 4 8 6 7 3 5 2;
             4 1 8 6 7 5 2 3;
                 ....]

then
% find indices of 1:8 in each row (assumes that each row is a permutation)
[B,B] = sort(A,2);
% convert to logical matrix for jobs in machine 1
B = B<5;
% weights of the set
W = 1./S;
M = sum(W);
% Put the following line into an appropriate loop
E(1,1) = sum(W(B(:,1)))/M;

Note that job i is either treated by machine 1 OR machine 2 so
E(i,2) = 1 - E(i,1);

The above -pseudo- code is completely untested but should be quick. Surely a bsxfun guru can improve further still.

Not really, actually I have problems with 12 machine and 120 jobs as well. Sometimes machines do not have the same number of jobs, some may have 1 more than others.

Anyone else out there may know how to improve this code? Thanks!

"Diego Zegarra" <diegozbb@gmail.com> wrote in message <gnjru2$e07$1@fred.mathworks.com>...
> Not really, actually I have problems with 12 machine and 120 jobs as well. Sometimes machines do not have the same number of jobs, some may have 1 more than others.
>
> Anyone else out there may know how to improve this code? Thanks!

Is the number of sequences known?

The number of sequences depend on the number of machines and jobs,

If there are 2 machines and 20 jobs then each machine is either going to have 10 jobs or one 9 and the other 11.

This means that there are 18 sequences no matter what, either 9 at each machine or 10 and 8.

There are still some aspects of your code that I don't understand, however I think the following pseudo-code will be reasonably fast. There are two quantities that I have left for you to compute, they are jobsJ and currJob.

% Calculate weights
Weight = 1./S
% Loop over all sequences
for k = 1:numSequences
% Loop over all machines
    for j = 1:numMachines
% Loop over the number of jobs in machine j, jobsJ
        for i = 1:jobsJ
% Obtain the i-th job from machine j, currJob, then

             E(currJob, j) = E( currJob, j) + Weight(k)
        end
    end
end

"Diego Zegarra" <diegozbb@gmail.com> wrote in message <gnlaer$p9d$1@fred.mathworks.com>...
> The number of sequences depend on the number of machines and jobs,
>
> If there are 2 machines and 20 jobs then each machine is either going to have 10 jobs or one 9 and the other 11.
>
> This means that there are 18 sequences no matter what, either 9 at each machine or 10 and 8.

% First advise: use array instead of cell.
% Second advice: call ACCUMARRAY as we showed you before.

clear
% Data
S =[110;109;115;107;113];
numMachines = 2;
numJobs = 8;
R=5;

S_Seq(:,:,1)=[1 4 8 6; 7 3 5 2];
S_Seq(:,:,2)=[4 1 8 6; 7 5 2 3];
S_Seq(:,:,3)=[3 7 8 6; 4 5 2 1];
S_Seq(:,:,4)=[8 6 2 5; 7 3 1 4];
S_Seq(:,:,5)=[1 5 3 6; 7 8 4 2];

% Create array of Machine
% have the same size as S_Seq
Machine = repmat((1:numMachines),[1 size(S_Seq,2) size(S_Seq,3)]);
% Schedule index, similarly...
SIdx = reshape((1:length(S)),1,1,[]);
SIdx = repmat(SIdx,[size(S_Seq,1) size(S_Seq,2) 1]);

T = sum(1./S);
% Engine
Ejk = accumarray([S_Seq(:) Machine(:)], SIdx(:), [numJobs numMachines], ...
                 @(idx) sum(1./S(idx)/T))

% Bruno

% Slighly clearer

clear
% Data
S =[110;109;115;107;113];
numMachines = 2;
numJobs = 8;

S_Seq(:,:,1)=[1 4 8 6; 7 3 5 2];
S_Seq(:,:,2)=[4 1 8 6; 7 5 2 3];
S_Seq(:,:,3)=[3 7 8 6; 4 5 2 1];
S_Seq(:,:,4)=[8 6 2 5; 7 3 1 4];
S_Seq(:,:,5)=[1 5 3 6; 7 8 4 2];

% Create array of Machine
% have the same size as S_Seq
% Schedule index, similarly...
[Machine Trash SIdx] = ndgrid(1:numMachines,1:size(S_Seq,2),1:length(S));

T = sum(1./S);
% Engine
Ejk = accumarray([S_Seq(:) Machine(:)], SIdx(:), [numJobs numMachines], ...
                 @(idx) sum(1./S(idx)/T))

% Bruno

> Ejk = accumarray([S_Seq(:) Machine(:)], SIdx(:), [numJobs numMachines], ...
> @(idx) sum(1./S(idx)/T))
>

Not very critical change, but the anonymous function looks better in this form:

@(idx) sum(1./S(idx)) / T

Bruno

% Even shorter

clear
S =[110;109;115;107;113];
numMachines = 2;
numJobs = 8;

S_Seq(:,:,1)=[1 4 8 6; 7 3 5 2];
S_Seq(:,:,2)=[4 1 8 6; 7 5 2 3];
S_Seq(:,:,3)=[3 7 8 6; 4 5 2 1];
S_Seq(:,:,4)=[8 6 2 5; 7 3 1 4];
S_Seq(:,:,5)=[1 5 3 6; 7 8 4 2];

% Engine
W = 1./S;
[Machine Trash W] = ndgrid(1:numMachines,1:size(S_Seq,2), W / sum(W));
% Engine
Ejk = accumarray([S_Seq(:) Machine(:)], W(:), [numJobs numMachines])

% Bruno

% Alternative last statement, Sparse matrix:
Ejk = sparse(S_Seq(:), Machine(:), W(:), numJobs, numMachines)

% Bruno

Bruno,

Thanks so much for your responses. Now could you please elaborate more on what each line is doing, it works perfect but I am trying to learn what is it that you did.

Additionally there is one thing in there that may change the thing. I had it in cell at first because the number of jobs in one machine is not necessarily going to be the same as the number of jobs in the other machine. In a problem of 2 machines and 20 jobs we may have 10 jobs at each machine or maybe 11 jobs at one and 9 at the other. Also in the case we have lets say 6 machines and 20 jobs, 4 machines will have 3 jobs and 2 machines will have 4 jobs. How could the code above be changed to be able to account for that? As you may see that is accounted in the code I wrote at first but it is not as fast.

Thanks again and I hope I made myself clear and that you can help me out with this.

"Diego Zegarra" <diegozbb@gmail.com> wrote in message <gnmt8e$r0s$1@fred.mathworks.com>...
> Bruno,
>
> Thanks so much for your responses. Now could you please elaborate more on what each line is doing, it works perfect but I am trying to learn what is it that you did.

I'm not good at explaining, and I'm sorry. You should work on your own, for example started from the first thread where we gave you few examples how to use ACCUMARRAY, which is easier to grab than the problem thread.

>
> Additionally there is one thing in there that may change the thing. I had it in cell at first because the number of jobs in one machine is not necessarily going to be the same as the number of jobs in the other machine. In a problem of 2 machines and 20 jobs we may have 10 jobs at each machine or maybe 11 jobs at one and 9 at the other. Also in the case we have lets say 6 machines and 20 jobs, 4 machines will have 3 jobs and 2 machines will have 4 jobs. How could the code above be changed to be able to account for that? As you may see that is accounted in the code I wrote at first but it is not as fast.
>

You can work with cells of course, but it will be less practical.

You could also fill empty places of the schedule vectors with a dummy job number (e.g., nbjob + 1) to form the array, then discard the dummy job once Ejk has been computed.

Though you need to think hard and make the right decision now about what kind of structure is most appropriate for your problem and its processing.

Bruno