a single machine scheduling problem

[ylxin1993]

Hi. when I do my home work, I'm stuck for hours, I hope you can read the requirement and exam my code and help me.

A very simple version of this general problem is a single machine scheduling
problem. We are given one machine, and a set of jobs to be processed on
the machine. No two jobs can be processed at the same time, and when we
start processing a job it cannot be interrupted in order to process another
job in between.
Each job j is characterized by a processing time pj and a weight wj , as
well as an id. A schedule is given by a start time Sj for each job j . A
schedule with start times Sj defines completion times Cj = Sj + pj
. The weights model the urgency of a job: we want to find a schedule of the jobs
on the machine such that the weighted sum of completion times, sum of wj * Cj ,is minimized. // (here is the final requirement)
A classical result by Smith, published in 1956, says that we can find an
optimal schedule as follows: sort the jobs by decreasing ratios wj/pj
and schedule them in this order. This rule is called the Smith Rule.

(a) Implement a class SingleMachineScheduling that contains all neces-sary member functions to handle single machine scheduling problems,
in which tasks have processing times and weights. In particular, the
class should offer the Smith-Rule as a member function, by which we
can compute an optimal schedule.

(b) Test your class  in the file SingleMachineExpl.txt. 
The file contains in the first row the num-ber of tasks, 
and then in each following row the id, the processing time 
and the weight of a job.

the SingleMachineExpl.txt:

15
1 4 2
2 3 0.1
3 8 0.7
4 3 1
5 6 2.0
6 10 2.7
7 9 3
8 14 7
9 13 5
10 2 7
11 4 3.0
12 8 2.5
13 9 4
14 12 6
15 13 4

here's my code:

class SingleMachineScheduling {
public:
	SingleMachineScheduling(string filename);
	~SingleMachineScheduling();

	void sort();
	double SmithRule();
private:
	int num;
	int* id;
	double* time;
	double* weight;
};

SingleMachineScheduling::SingleMachineScheduling(string filename) { 
	num = 0;
	ifstream in(filename.c_str());
	in >> num;
	id = new int[num];
	time = new double[num];
	weight = new double[num];

	for(int i = 0; i < num / 3; ++i) {  // is my reading style good? or a better way?
		int j = 3 * i;
		for(; j < 3 + 3 * i; ++j)
			in >> id[j];
		j = 3 * i;
		for(; j < 3 + 3 * i; ++j)
			in >> time[j];
		j = 3 * i;
		for(; j < 3 + 3 * i; ++j)
			in >> weight[j];
	}

}

SingleMachineScheduling::~SingleMachineScheduling() {
	delete [] weight;
	delete [] time;
}

void SingleMachineScheduling::sort() {  // I don't know how to sort the array
	// double temp[num];               // it needs sort two array, I'm crashed
	//for(int i = 0; i < num; ++i) {   // I don't know how to sort the 2 array, it stucks me long hours
	//	temp[i] = weight[i] / time[i];
	//}
}

double SingleMachineScheduling::SmithRule() {
	sort();
	double c = 0.0;
	double optimal = 0.0;
	for(int i = 0; i < num; ++i) {
		c += time[i];
		optimal += weight[i] * c;
	}
	return optimal;
}

[Darkmaster]

#include<algorithm>

std::sort(temp, &temp[size]); //your array is called temp right?

if you don't know the size, use
std::sort(temp, &temp[sizeof(temp)/sizeof(temp[0])]);

[ylxin1993]

Hi,

Darkmaster

, I'm sorry I didn't make me code clear, and I rewrite it.
first, I think my sort method is writed wrong, the requirement is

sort the jobs by decreasing ratios wj/pj and schedule them in this order.

, I just don't how to schedule the weight and time array after rearrange by wj/pj.

[Darkmaster]

just to be sure:
you want to sort weight, time and id, from highest weight[i]/time[i] to lowest weight[i]/time[i] ?

[ylxin1993]

I think the SimtiRule:

sort the jobs by decreasing ratios wj/pj and schedule them in this order.

is to sort the id, weight, time by wj/pj(which is weight[j] / time[j]), but I don't know how to rearrange them by wj / pj

[Darkmaster]

try this:

#include<algorithm>

int main()
{
	int weight[5] = {5,3,4,2,1};
	int time[5] = {3,5,1,2,4};
	int id[5] = {1,2,3,4,5};

	for(int i=5-1; i>=1; --i)
	{
		int index = i;
		for(int j=i-1; j>=0; --j)
		{
			if((weight[j]/time[j]) > (weight[index]/time[index]))
				{index = j;}
		}
		std::swap(weight[i], weight[index]);
		std::swap(time[i], time[index]);
		std::swap(id[i], id[index]);
	}
}

if the order is reversed you need to change line 9, 12 and 14

[ylxin1993]

Hi,

Darkmaster

, I want to write this code in a class method, what should I do?


this doesn' t work, it can't rearrange correctly

void SingleMachineScheduling::sort() {

	for(int i = num - 1; i >= 0; --i) {
		int index = i;
		for(int j = i - 1; j >= 0; --j) {
			if((weight[j]/time[j]) > (weight[index]/time[index]))
				index = j;
		}
		std::swap(weight[i], weight[index]);
		std::swap(time[i], time[index]);
		std::swap(id[i], id[index]);
}
	}