### a single machine scheduling problem

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.
 ``1234567891011121314151617181920212223`` ``````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:
 ``12345678910111213`` ``````class SingleMachineScheduling { public: SingleMachineScheduling(string filename); ~SingleMachineScheduling(); void sort(); double SmithRule(); private: int num; int* id; double* time; double* weight; };``````

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344`` ``````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; }``````
Last edited on
#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])]);
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.
just to be sure:
you want to sort weight, time and id, from highest weight[i]/time[i] to lowest weight[i]/time[i] ?
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
try this:

 ``123456789101112131415161718192021`` ``````#include 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
Last edited on
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
 ``12345678910111213`` ``````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]); } }``````
Topic archived. No new replies allowed.