## 1194 - Machine Schedule

All about problems in Volume 11. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

jaywinyeah
New poster
Posts: 19
Joined: Sun Aug 17, 2003 10:40 pm

### Re: 1194 - Machine Schedule

I have a simple recursive algorithm that brute-forces, trying to put each job either on machine1 or machine2. Since there are k jobs, this is O(2^k). I have the "optimization" of eliminating the job choice if either machine was previously in the required mode, which reduces the runtime to O(2^(m+n)). With k<=1000, m<=100, and n<=100, this is not even close to an acceptable runtime. Any help in simplifying the problem domain would be greatly appreciated. Here's what I have so far:

Code: Select all

private int countRestarts(int [][] jobs, int modes1, int modes2)
{
boolean [] used1 = new boolean [modes1];
boolean [] used2 = new boolean [modes2];
used1[0] = used2[0] = true;
int count = countRestarts(jobs, 0, used1, used2);
return count;
}

private int countRestarts(int [][] jobs, int jobIndex, boolean [] used1, boolean [] used2)
{
if(jobIndex == jobs.length)
return 0;
else
{
//see if free job
int job1 = jobs[jobIndex][1];
int job2 = jobs[jobIndex][2];
if(used1[job1] || used2[job2])
return countRestarts(jobs, jobIndex + 1, used1, used2);
else
{
//try machine1
used1[job1] = true;
int result1 = 1 + countRestarts(jobs, jobIndex + 1, used1, used2);
used1[job1] = false;

//try machine2
used2[job2] = true;
int result2 = 1 + countRestarts(jobs, jobIndex + 1, used1, used2);
used2[job2] = false;

return Math.min(result1, result2);
}
}
}
Thanks.
Jason Winokur
LL Cool Jay
The Formula Wizard
Jason Winokur

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

### Re: 1194 - Machine Schedule

I solved this one using network flow. (Bipartite matching)

BTW, I wrote a input generator.

Code: Select all

#include<bits/stdc++.h>
using namespace std;

int main()
{
srand( time( NULL ) );

for( int t = 0; t < 10000; ++t )
{
int A = rand() % 50 + 1, B = rand() % 50 + 1, Q = rand() % ( A*B ) + 1;
printf( "%d %d %d\n", A, B, Q );
while( Q-- )
printf( "%d %d %d\n", Q, rand() % A, rand() % B );
puts( "" );
}
putchar( '0' );
}
Life shouldn't be null.