#define M 6						// Number of machines
#define JOBS M					// Number of jobs
#define TASKS JOBS 				// Number of tasks
#define ITERATIONS 12				// Number of randomized runs

int duration[JOBS][TASKS];				// Time to run task t of job j
int task_time[M][JOBS];					// Time to run job j’s task on m 
int machine[JOBS][TASKS];				// Machine for task t of job j

continuous FinTime[M][JOBS];			// Finish of j"s task on m  
continuous MakeSpan; 					// Finish of last task

data()	// 6 by 6
{
	duration = {
		1,3,6,7,3,6,
		8,5,10,10,10,4,
		5,4,8,9,1,7,
		5,5,5,3,8,9,
		9,3,5,4,3,1,
		3,3,9,10,4,1
	};

	machine = {
		2,0,1,3,5,4,
		1,2,4,5,0,3,
		2,3,5,0,1,4,
		1,0,2,3,4,5,
		2,1,4,5,0,3,
		1,3,5,0,4,2
	};

	and(int j=0;j<JOBS;j++)
		and(int t=0;t<TASKS;t++)
			task_time [machine[j][t]] [j] =  duration[j][t];
}

setup()
{
	and(int jb=0;jb<JOBS;jb++)
		and(int tsk=0;tsk<TASKS;tsk++) 
			duration[jb][tsk]
				<= FinTime[machine[jb][tsk]][jb];

	and(int jb=0;jb<JOBS;jb++)
		and(int tsk=0;tsk<TASKS-1;tsk++) 
			FinTime[machine[jb][tsk]][jb] 
			+ duration[jb][tsk+1]
			<= FinTime[machine[jb][tsk+1]][jb];

	and(int jb=0;jb<JOBS;jb++)
       		MakeSpan >= FinTime[machine[jb][TASKS-1]][jb];
}

schedule(continuous Ft[],int time[])
{
int p[JOBS]; 

	and(int j=0;j<JOBS;j++)
		p[j] = j;

	and(int i=0;i<JOBS;i++){
		pick_next_job(i,p,Ft,time);
		if i > 0; 
		then Ft[p[i-1]] + time[p[i]] <= Ft[p[i]];
	}
}

pick_next_job(int i, int p[], continuous Ft[], int time[])
{
double prize;
	prize = 1e6;
	and(int j=i;j<JOBS;j++) {
		if not {			// Try for improvement
			if i > 0; 						// p[0],...,p[i-1] already scheduled
			then Ft[p[i-1]] + time[p[j]] <= Ft[p[j]];
			and(int k=i;k<JOBS;k++) 			// Try job j’s task first 
				if p[k] != p[j];					
				then Ft[p[k]] >= Ft[p[j]] + time[p[k]];
			min: MakeSpan;
			wp(MakeSpan) < prize; 			// Better evaluation ?
			switch(i,j,p,prize);				// Then take first place
		} 
		then ;			// If no improvement, do nothing
	}
}

switch(int i,j, p[], double & prize)
{
int winner;

	winner = p[j]; 
	p[j] = p[i]; 
	p[i] = winner;
	prize = wp(MakeSpan); 
}

find_next_random_sequence(int q[], int n)
{
int temp, rand;

	and(int i=0;i<n;i++) 
		q[i] = i;
	and(int i=0;i<n;i++) {
		rand = random()*n-i; 		// random integer 
								// between 0 and n-i-1
		temp = q[i+rand];
		q[i+rand] = q[i];
		q[i] = temp;
	} 
}

random_run(int k, double & best)
{
int q[M];

 	printf("Entering iteration %d\n",k);

	find_next_random_sequence(q,M); 			// Order the machines
	MakeSpan <= best-1;						// Force the issue
	and(int i=0;i<M;i++)							// Heuristic
		schedule(FinTime[q[i]],task_time[q[i]]);
	min: MakeSpan; 							// To store best possible value
	best = wp(MakeSpan);						// Record result
}

sequence_jobs()
{
	and(int m=0;m<M;m++)							// On each machine i
		and(int jb=0;jb<JOBS;jb++)					// for each pair of jobs
			and(int k=0;k<jb;k++)					// run only one at a time
				either 
					FinTime[m][jb] + task_time[m][k]
					<= FinTime[m][k];
				or 
					FinTime[m][k] + task_time[m][jb]
					<= FinTime[m][jb];
}

best_schedule()
{
double target;

	target = 57;			// Known bound
	and(;;) {				// Indefinite loop
		if not {			// Try to meet challenge  
			MakeSpan <= target-1;				// Challenge bound
			sequence_jobs();					
			min: MakeSpan;					// Do the best you can
			target = wp(MakeSpan);				// Record new bound
		}
		then break;			// Bound too strong, exit loop
	}
	printf("The best possible makespan is %f\n",target);
}

2lp_main()
{
	data();
	setup();
	best_schedule();
}
 