Probleme bei der Umsetzung einer Heuristik

[beginner58]

Hallo liebe Forennutzer,

ich habe Probleme die Greedy Random Adaptive Search Procedure Heuristik in c++ umzusetzen. Und zwar habe ich bei Folgendem besonders Schwierigkeiten. Es soll eine Reihenfolge von Jobs gebildet werde. Welcher Job ausgewählt wird als jeweils nächster hängt davon ab, wie sich der makespan (also die gesamte Bearbeitungszeit der bisher vorhandenen Jobs) durch Hinzufügen des jeweiligen Jobs erhöht. Entsprechend einer Funktion kommen bestimmte Jobs in Betracht und werden zufällig ausgewählt. Ich schaffe es jedoch nicht richtig, die Startlösung zu konstruieren, da ich immer Fehler entstehen bei der Berechnung des aktuellen Makespans ausgehend von den bisher ausgewählten Jobs.
Ich habe 5 Maschinen und 20 Jobs, die auf diesen Maschinen ausgeführt werden sollen.

Mein bisheriger Code sieht folgendermaßen aus und funktioniert bis zum 2. <schritt, ab da gibt es Probleme und irgendwann geht es gar nciht mehr.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <numeric>
#include <iterator>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <time.h>
#include <cstdlib>

using namespace std;

void width(vector<int>&Makespan, double alpha, vector<int>&avjobs, vector <int>&RCL, int Durchlauf)
{
	int min = *min_element(Makespan.begin()+Durchlauf,Makespan.end()); // Finden des Minimums und Maximums des Vektors Makespan
	int max = *max_element(Makespan.begin()+Durchlauf,Makespan.end());
	cout << "Min ist " << min << endl;
	cout << "Max ist " << max << endl;
	double width;
	width=alpha*(max-min);
	cout << width << endl;
	cout << "Die jobs: ";
	for (int i=0+Durchlauf; i<avjobs.size();i++) 
	{
		double neu;
		neu=min+width;
		if (Makespan[i] < neu)
		{
			RCL.push_back(avjobs[i-Durchlauf]);
		}
	}
}

void CompletionM1 (vector <int> &proctimes, vector <int> &Cm1, vector <int> &Cm2, int nbrmach, int jobnbr, int Durchlauf)
{
	int summeneu, summe=0; int jobs; int neu;

	if (Durchlauf==0)
	{
		Cm1[0+nbrmach*Durchlauf]=(Cm1[0]+proctimes[(jobnbr)*nbrmach]);

		for (jobs=1; jobs < 5; jobs++)
	{
		neu = Cm1[jobs];
		summeneu = max (neu, Cm1[jobs-1]) + proctimes [(jobnbr*nbrmach)+jobs];
		summe = summeneu;
		Cm1[jobs+nbrmach*Durchlauf]=(summeneu);
	}
	Cm2.push_back(Cm1.back());

	} else

		{	Cm1[0+nbrmach*Durchlauf]=(Cm1[0]+proctimes[(jobnbr)*nbrmach]);

	for (jobs=1; jobs < 5; jobs++)
	{	
		neu = Cm1[jobs+(nbrmach*Durchlauf)-5];
		summeneu = max (neu, Cm1[jobs+(nbrmach*Durchlauf)-1]) + proctimes [(jobnbr*nbrmach)+jobs];
		summe = summeneu;
		Cm1[jobs+nbrmach*Durchlauf]=(summeneu);
	}
	Cm2.push_back(Cm1.back());

//}
}
}

int main ()
{
	vector <int> proctimes;
	srand(time(NULL));

ifstream infile1  ("C:/Users/ich/Documents/Uni/C++/Taillard20_5.txt");
  if(!infile1.is_open()){ 
    cerr << "Fehler beim Oeffnen der Datei.\n"; 
    return -1; 
  } 
  // drei Zeilen konsumieren und ignorieren 
  for(int i=0; i<3; ++i) 
    infile1.ignore(numeric_limits<streamsize>::max(), '\n'); 

	string line1;

	while ( getline (infile1,line1) )
    {
      stringstream s (line1);
	  int tmp;

	  while (s>>tmp) {
		proctimes.push_back(tmp);  
    }
}

	infile1.clear(); // Fehlerstatus auf 0 setzen
	infile1.close(); // File schließen

	// +++++++++++++++++++++++++Vektoren+++++++++++++++++++++++++++++++++++++++
	vector <int> neu; int nbrjobs=20; int nbrmach=5;

	for (int i=0; i<nbrjobs; i++) // Vektorelemente so anordnen, als wären sie spaltenweise eingelesen worden
	{
		neu.push_back(proctimes.at(i)); neu.push_back(proctimes.at(i+20)); neu.push_back(proctimes.at(i+40)); neu.push_back(proctimes.at(i+60)); neu.push_back(proctimes.at(i+80));
	}

	/*copy(neu.begin(), neu.end(), ostream_iterator<int>(cout, " ")); */

	cout << endl;

	vector <int> Completion; vector <int> Makespan; vector <int> avjobs;

	for (int i=1; i<=5; i++) Completion.push_back(0);

	/*for (int i=1; i<=20; i++) Makespan.push_back(0);*/

	for (int i=1; i<=20; i++) avjobs.push_back(i); // Füllen des Vektors avjobs mit allen verfügbaren Jobs

	for (int i=0; i<avjobs.size(); i++) // Für alle verfügbaren Jobs die jeweiligen Completiontimes berechnen und die Endergebnisse der einzelnen Jobs im Vektor Makespan speichern
	{
	CompletionM1(neu, Completion, Makespan, 5, i, 0);
	Completion.clear();
	for (int i=1; i<=5; i++) Completion.push_back(0);
	}

	cout<< "Vektor Completion: "; // Kontrollausgabe alles erzeugten Completiontimes mit Zwischensummen

	for (int i=0; i<Completion.size();i++)
	{
		cout << Completion [i] << " ";
	}
	cout << endl;

	cout << "Completiontimes aller 20 Jobs: ";
	for (int i=0; i<Makespan.size();i++)
	{
		cout << Makespan [i] << " ";
	}
	cout << endl;

	vector <int> RCL;
	width(Makespan, 0.5, avjobs, RCL,0);

	for (int i=0;i<RCL.size();i++)
	{
		cout << RCL[i] << " ";
	}
	cout << "liegen im Bereich."<<endl;
	int randI = rand() % RCL.size();
	cout << "Job: " << RCL[randI] <<endl;
	vector<int>Lsg;
	Lsg.push_back(RCL[randI]);

	for (int i=0; i<Lsg.size();i++)
	{ cout << Lsg[i];}

	// Löschen des i-ten Elementes aus den verfügbaren Jobs
	avjobs.erase (avjobs.begin()+(RCL[randI])-1);

	Makespan.clear();
	CompletionM1(neu, Completion, Makespan, 5, RCL[randI]-1, 0);  // Die gefundene Lösung in den Vektor Completion

	for (int i=1; i<=5; i++) Completion.push_back(0);

  RCL.clear();

  for (int i=0; i<avjobs.size();i++)
  {
  cout << avjobs[i] << " ";
  }

  // ++++++++++++++++++++++++++++++++++++++Durchgang 2+++++++++++++++++++++++++++++++++++++

  for (int j=1;j<nbrjobs;j++)
  {
	for (int i=0; i<avjobs.size(); i++) // Für alle verfügbaren Jobs die jeweiligen Completiontimes berechnen und die Endergebnisse der einzelnen Jobs im Vektor Makespan speichern
	{
		int k=avjobs[i]-1;
	CompletionM1(neu, Completion, Makespan, 5, k, j);
	/*Completion.erase(Completion.begin()+5, Completion.end());
	for (int i=1; i<=5; i++) Completion.push_back(0);*/
	}

	cout<< "Vektor Completion: "; // Kontrollausgabe alles erzeugten Completiontimes mit Zwischensummen

	for (int i=0; i<Completion.size();i++)
	{
		cout << Completion [i] << " ";
	}
	cout << endl;

	cout << "Completiontimes aller 20 Jobs: ";
	for (int i=0; i<Makespan.size();i++)
	{
		cout << Makespan [i] << " ";
	}
	cout << endl;

	width(Makespan, 0.5, avjobs, RCL,j);

	for (int i=0;i<RCL.size();i++)
	{
		cout << RCL[i] << " ";
	}
	cout << "liegen im Bereich."<<endl;
	randI = rand() % RCL.size();
	cout << "Job: " << RCL[randI] <<endl;

	Lsg.push_back(RCL[randI]);

	for (int i=0; i<Lsg.size();i++)
	{ cout << Lsg[i];}

	// Löschen des i-ten Elementes aus den verfügbaren Jobs
	avjobs.erase (avjobs.begin()+(RCL[randI])-1);
	Makespan.erase(Makespan.begin()+1,Makespan.end());
	Completion.erase(Completion.begin()+5,Completion.end());
	for (int i=1; i<=5; i++) Completion.push_back(0);
	CompletionM1(neu, Completion, Makespan, 5, RCL[randI]-1, 1);  // Die gefundene Lösung in den Vektor Completion
	for (int i=1; i<=5; i++) Completion.push_back(0);

  RCL.clear();

  for (int i=0; i<avjobs.size();i++)
  {
  cout << avjobs[i] << " ";
  }
  for (int i=0; i<Completion.size();i++)
  {
  cout << Completion[i] << " ";
  }
  for (int i=0; i<Makespan.size();i++)
  {
  cout << Makespan[i] << " ";
  }
  }
  }

Wahrscheinlich ist die Aufgabe zu komplex, um mal schnell drüber zu schauen, aber vllt kann mir ja doch jmd behilflich sein. Ich würde mich freuen.

[Furble Wurble]

Ohne Eingabedatei ist viel Spekulation dabei.
Besonders, wenn Du beschreibst:

beginner58 schrieb:

funktioniert bis zum 2. <schritt, ab da gibt es Probleme und irgendwann geht es gar nciht mehr

Ich habe mir gerade mal eine Eingabedatei aus 23 mal der Zahl 5 gebaut - und prompt flog mir ein subscript ( at() ) um die Ohren...

Diese Zugriffe auf vermeintlich vorhandene Vektorelemente, sind auf jeden Fall eine dankbare Quelle für Abstürze.

Es ist auch ein rechter Spaghetticode geworden... ein paar mehr Funktionen wären gut, z.B. für die Ausgabe eines std::vectors auf cout .
Mehr Struktur u. weniger Zeilen machen das debuggen leichter.