Dev - C++ - Taillard en C++17 - Zinjai

#include <bits/stdc++.h>

using namespace std;

int nJobs;

int mMach;

std::vector < int > p;

mt19937 mRand (random_device{}()+time(0));

// mide el tiempo (en milisegundos) transcurrido

// desde elapsed(true) hasta elapsed()

inline int elapsed(bool reset = false)

{

	static clock_t start = clock();

	if ( reset ) start = clock();

	return (1000.00*double(clock()-start))/double(CLOCKS_PER_SEC);

}

// Genera una permutación de trabajos

// con el orden no creciente de sus tiempos totales.

void NEH_priority ( vector < int > & prt )

{

	vector < int > T;

	prt.resize((nJobs));

	T.resize((nJobs));

	vector < int > ::iterator po = p.begin();

	// Calculate total time for each job.

	for ( auto & t : T )

	{

		int S1 = 0;

		for (vector < int > ::iterator _po = po + mMach; po < _po; ++po) S1 += (*po);

		t = S1;

	}

	iota(prt.begin(),prt.end(),0);

	std::sort( prt.begin(), prt.end(),

		[&T](const int & i, const int & j) { return (T[(i)]>T[(j)] ||(T[(i)]==T[(j)] && i<j)); } );

}

// Determina el mejor punto de inserción bj

// del trabajo jo en una solución parcial [b,e]

// utilizando la aceleración de Taillard (1990).

#define UNFOLDFOR2( __iters__, __sentences__ ) for (int ___my_cnt = __iters__ - 1; ___my_cnt; --___my_cnt  ) { __sentences__ }

vector<int>::iterator itBestInsertionPoint (

		vector<int> & sol,

		const int jo )

{

	static vector< int > Me0, Me1, Mq0;

	vector < int > ::iterator to, me0, lm, me1, mq0;

	vector < int > ::iterator bj = sol.begin();

	Me0.resize(uint_fast32_t (750*mMach));

	Me1.resize(uint_fast32_t (750*mMach));

	Mq0.resize(uint_fast32_t (750*mMach));

	for ( me0  = Me0.begin() - 1, lm = me0+mMach; me0 <= lm;) *(++me0) = 0;

	// Función lambda que prepara el cálculo de tiempos q.

	auto __PropagateMiB0 = [&] ()

	{

		mq0 = lm = Mq0.begin() + uint_fast32_t(int(sol.end()-sol.begin()+1) * mMach);

		UNFOLDFOR2 ( mMach, { *(--mq0) = 0; } ); { *(--mq0) = 0; }

	};

	// Función lambda que calcula tiempos q.

	auto __PropagateMiB = [&] ( int & op )

	{

		vector < int > ::iterator t = p.begin() + uint_fast32_t(op*mMach + mMach - 1);

		int lt = *(--mq0) = *(--lm) + *t;

		UNFOLDFOR2 ( mMach, { if ( lt < *(--lm) ) lt = *lm; *(--mq0) = ( lt += *(--t) ); } );

	};

	// Función lambda que prepara el cálculo de tiempos e, f y makespan mxt.

	auto __PropagateMiA0 = [&] ()

	{

		lm = Me0.begin() - 1;

		me0 = lm + mMach;

		me1 = Me1.begin();

		vector < int > ::iterator t = to;

		int lt = *me1 = *t;

		int mxt = *mq0 + *me1;

		UNFOLDFOR2 ( mMach, { int cmt = *(++mq0) + ( *(++me1) = ( lt += *(++t) ) ); if ( mxt <= cmt ) mxt = cmt; } );

		return mxt;

	};

	// Función lambda que calcula tiempos e, f y makespan mxt.

	auto __PropagateMiA = [&] ( int & op )

	{

		vector < int > ::iterator jt = to;

		vector < int > ::iterator t = p.begin() + uint_fast32_t(op*mMach);

		int lt = *(++me0) = *(++lm) + *t;

		int llt = *(++me1) = lt + *(jt);

		int mxt = *(++mq0) + llt;

		UNFOLDFOR2 ( mMach, { if ( lt < *(++lm) ) lt = *lm; lt += *(++t); *(++me0) = lt; if ( llt < lt ) llt = lt; llt += *(++jt); int cmt = *(++mq0) + ( *(++me1) = llt );  if ( mxt <= cmt ) mxt = cmt; } );

		return mxt;

	};

	/////////////////// CalculateBestInsertionPoint comienza aquí ///////////////////

	to = p.begin() + uint_fast32_t(jo*mMach);// tiempos de las operaciones a insertar

	// Calcula hacia atrás los tiempos q

	{

		__PropagateMiB0 ();

		for ( vector < int > ::iterator op = sol.end()-1, _op = sol.begin() - 1; op > _op; --op)

			__PropagateMiB ( *op );

	}

	// Calcula hacia adelante los tiempos e, f, y makespan mxt

	{

		// guarda el primer tiempo y la primer posición,

		int mejormxt = __PropagateMiA0 ();

		bj = sol.begin();

		for ( vector < int > ::iterator op = bj; op < sol.end(); )

		{

			// revisa el makespan de la siguiente posición

			int mxt = __PropagateMiA ( *op ); ++op;

			// Actualiza el mejor resultado encontrado si hay mejora

			if ( mxt < mejormxt )

			{

				mejormxt = mxt;

				bj = op;

			}

		}

	}

	return bj; // retorna la mejor posición de inserción

}

void leerArchivo(string nombreArchivo)

{

	ifstream infile(nombreArchivo);

	infile >> nJobs;

	infile >> mMach;

	if (nJobs*mMach < 10) {cout << "WRONG FILE!!";exit(1);}

	p.resize(nJobs*mMach);

	for(vector<int>::iterator t=p.begin(); t<p.end(); t++)

	{

		int basura;

		infile >> basura;

		infile >> *t;

	}

}

int Cmax ( vector<int> & sol )

{

	vector <int> C;

	C.resize((nJobs+1)*mMach);

	fill (C.begin(), C.begin()+mMach, 0);

	vector <int>::iterator actual = C.begin()+mMach;

	for ( auto j : sol )

	{

		vector <int>::iterator op = p.begin() + j*mMach;

		*actual = *(actual-mMach) + *op;

		for(int i = mMach-1; i; --i)

		{

			actual++; op++;

			int mx = ( *(actual-mMach) > *(actual-1) ) ? *(actual-mMach): *(actual-1);

			*actual = mx + *op;

		}

		actual++;

	}

	return *(actual-1);

}

main()

{

	leerArchivo("flowshop/br66");

	// ejemplo de uso de itBestInsertionPoint

	std::vector<int> sol = {4,3,1,0};

	for(auto j : sol){cout<<" "<<j;} cout<<" "<<Cmax(sol)<<endl;

	sol.insert( itBestInsertionPoint(sol, 2) ,2);

	for(auto j : sol){cout<<" "<<j;} cout<<" "<<Cmax(sol)<<endl;

	// ejemplo de uso de NEH_priority

	NEH_priority ( sol );

	for(auto j : sol){cout<<" "<<j;} cout<<endl;

}