1194 - Machine Schedule

[jaywinyeah]

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

[dibery]

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' );
}