Job Scheduling (Bài toán phân công công việc)


#include <iostream>
using namespace std;
#define MAX 30

class Job{
public:
int time;
int index;
};
class Machine{
public:
int totalTime; // total of time
int numberOfJob;
Job job[MAX];
};

void Input(Job job[], int numberOfJob){
int i;
for(i=0; i<numberOfJob; i++){
cout << "Input work time for job: " << i+1 << ":"; job[i].index = i+1; cin >> job[i].time;
}
}
void OutputEachJob(Job job[], int numberOfJob){
int i;
for(i=0; i<numberOfJob; i++){
cout << " [" << job[i].index << "] = " << job[i].time;
}
}

void JobSwapper(Job &job1, Job &job2){
Job temp;
temp.time = job1.time; job1.time = job2.time; job2.time = temp.time;
temp.index = job1.index; job1.index = job2.index; job2.index = temp.index;
}

void JobSorter(Job job[], int numberOfJob){
int i,j;
for(i=0; i<numberOfJob-1; i++){
for(j=i+1; j<numberOfJob; j++){
if(job[i].time < job[j].time){
JobSwapper(job[i], job[j]);
}
}
}
}

void MachineInitilize(Machine machine[], int numberOfMachine){
int i;
for(i=0; i<numberOfMachine; i++){
machine[i].totalTime = 0;
machine[i].numberOfJob = 0;
}
}

int FindMachineWorkInMinimumTime(Machine machine[], int numberOfMachine){
int i, f = 0;
int min = machine[0].totalTime;
for(i=1; i<numberOfMachine; i++){ if(min > machine[i].totalTime){
min = machine[i].totalTime;
f = i;
}
}
return f;
}

void JobScheduler(Machine machine[], int numberOfMachine, Job job[], int numberOfJob){
int f, k, i;
for(i=0; i<numberOfJob; i++){
// choose machine which is worked in minimum time
f = FindMachineWorkInMinimumTime(machine, numberOfMachine);
// the number of job that the selected machine done
k = machine[f].numberOfJob;
// add the next job for the selected machine
machine[f].totalTime += job[i].time;
machine[f].job[k].time = job[i].time;
machine[f].job[k].index = job[i].index;
machine[f].numberOfJob++;
}
}

void OutputResult(Machine machine[], int numberOfMachine){
int i, j;
int max = machine[0].totalTime;
for(i=0; i<numberOfMachine; i++){
if(max < machine[i].totalTime){
max = machine[i].totalTime;
}
cout << endl << "Machine " << i+1 << ":";
cout << endl << "Total time: " << machine[i].totalTime;
cout << endl << "Job process: ";
for(j=0; j<machine[i].numberOfJob; j++){
cout << "[" << machine[i].job[j].index <<"] ";
}
}
cout << endl << "\nBest time to finish all job: " << max << endl;
cout << endl;
}

int main()
{
Job job[MAX];
Machine machine[MAX];
int numberOfMachine, numberOfJob;

cout << ":: JOB SCHEDULING PROBLEMS ::" << endl;
do{
cout << "Input the number of machine (0 < N < 30): "; cin >> numberOfMachine;
cout << "Input the number of Job (0 < N < 30): "; cin >> numberOfJob;
}while((numberOfMachine < 0 || numberOfMachine > 30) || (numberOfJob < 0 || numberOfJob > 30));

MachineInitilize(machine, numberOfMachine);
Input(job, numberOfJob);
JobSorter(job, numberOfJob);
JobScheduler(machine, numberOfMachine, job, numberOfJob);
OutputResult(machine, numberOfMachine);

return 0;
}

Advertisements

One thought on “Job Scheduling (Bài toán phân công công việc)

  1. Pingback: Artificial intelligence | David Ng

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s