timelpt1.cpp

数据结构c++语言描述 Borland C++实现

#include<iostream.h>
#include<stdlib.h>
#include <time.h>
#include "hsort.h"
#include "minheap.h"

struct  JobNode {
           int ID, time;
           operator int () const {return time;}
           };

struct  MachineNode {
           int ID, avail;
           operator int () const {return avail;}
           };


template <class type>
void LPT(type *a, int n, int m)
{// Construct an m machine LPT schedule
MinHeap<MachineNode> H(m);
MachineNode x;
if (n <= m) {
   cout << "schedule one job per machine" << endl;
   return;}
HeapSort(a,n); //in ascending order
int i;
for (i = 1; i <= m; i++) //initialize machines
   {x.avail = 0; x.ID = i; H.Insert(x);}
//construct schedule
for (i = n; i >= 1; i--) {
   H.DeleteMin(x);
//   cout << "Schedule job " << a[i].ID << " on machine "
//        << x.ID << " from " << x.avail << " to "
//        << x.avail + a[i].time << endl;
   x.avail += a[i].time;
   H.Insert(x);
   }
}

void main(void)
{
JobNode a[10000];
//n is number of jobs, m is number of machines
//r is max job time
int n = 10000, r = 100, m = 100;
//initialize n jobs
for (int i=1; i<=n; i++) {a[i].time = 1 + random(r); a[i].ID = i;}
clock_t start, finish;
start = clock( );
int counter = 0; float seconds;
while (clock( ) - start < 10) {//at least 10 ticks
counter++;
LPT(a,n,m);
}
finish = clock( );
seconds = (finish - start) / CLK_TCK;
cout << n << ' ' << counter << ' ' << seconds
     << ' ' << seconds / counter << endl;
}