Example: open-shop scheduling More...

Classes
class	PrintTask
	Helper class for representing tasks when printing a solution. More...
class	Task
	Task representation for CROSH heuristic More...

Public Types
enum	{ SEARCH_BAB, SEARCH_RESTART }
	Search variants. More...

Public Member Functions
	OpenShop (const SizeOptions &opt)
	The actual problem.
	OpenShop (bool share, OpenShop &s)
	Constructor for cloning s.
virtual Space *	copy (bool share)
	Perform copying during cloning.
virtual IntVar	cost (void) const
	Minimize the makespan.
virtual void	print (std::ostream &os) const
	Print solution.
Public Member Functions inherited from Gecode::Driver::ScriptBase< BaseSpace >
	ScriptBase (void)
	Default constructor.
	ScriptBase (bool share, ScriptBase &e)
	Constructor used for cloning.
virtual void	compare (const Space &, std::ostream &os) const
	Compare with s.

Protected Member Functions
void	crosh (Matrix< IntArgs > &dur, int &minmakespan, int &maxmakespan)
	Use Constructive Randomized Open-Shop Heuristics to compute lower and upper bounds.

Protected Attributes
const OpenShopSpec &	spec
	The instance specification.
BoolVarArray	b
	Precedences.
IntVar	makespan
	Makespan.
IntVarArray	_start
	Start times.

Related Functions
(Note that these are not member functions.)
int	main (int argc, char *argv[])
	Main-function.

Open shop specifications
Each specification gives the processing times of the tasks for each job, as well as the number of jobs and machines.
const int	ex0_p []
	The instances.
const int	ex1_p []
	The instances.
const int	ex2_p []
	The instances.
const int	ex3_p []
	The instances.
const int	ex4_p []
	The instances.
OpenShopSpec	examples [] = { ex0, ex1, ex2, ex3, ex4 }
	The instances.
const unsigned int	n_examples = sizeof(examples) / sizeof(OpenShopSpec)
	The number of instances.
OpenShopSpec	ex0 (3, 3, ex0_p)
	The instances.
OpenShopSpec	ex1 (4, 4, ex1_p)
	The instances.
OpenShopSpec	ex2 (4, 4, ex2_p)
	The instances.
OpenShopSpec	ex3 (7, 7, ex3_p)
	The instances.
OpenShopSpec	ex4 (20, 20, ex4_p)
	The instances.

Additional Inherited Members
Static Public Member Functions inherited from Gecode::Driver::ScriptBase< BaseSpace >
template<class Script , template< class > class Engine, class Options >
static void	run (const Options &opt)

Detailed Description

Example: open-shop scheduling

Definition at line 68 of file open-shop.cpp.

Member Enumeration Documentation

anonymous enum

Search variants.

Enumerator:

SEARCH_BAB	Use branch and bound to optimize.
SEARCH_RESTART	Use restart to optimize.

Definition at line 196 of file open-shop.cpp.

Constructor & Destructor Documentation

OpenShop::OpenShop ( const SizeOptions & opt )

inline

The actual problem.

Definition at line 201 of file open-shop.cpp.

OpenShop::OpenShop	(	bool	share,
		OpenShop &	s
	)

inline

Constructor for cloning s.

Definition at line 254 of file open-shop.cpp.

Member Function Documentation

void OpenShop::crosh	(	Matrix< IntArgs > &	dur,
		int &	minmakespan,
		int &	maxmakespan
	)

inlineprotected

Use Constructive Randomized Open-Shop Heuristics to compute lower and upper bounds.

This heuristic is taken from the paper A. Malapert, H. Cambazard, C. Gueret, N. Jussien, A. Langevin, L.-M. Rousseau: An Optimal Constraint Programming Approach to the Open-Shop Problem. Technical report, CIRRELT-2009-25.

Definition at line 100 of file open-shop.cpp.

virtual Space* OpenShop::copy ( bool share )

inlinevirtual

Perform copying during cloning.

Definition at line 262 of file open-shop.cpp.

virtual IntVar OpenShop::cost ( void ) const

inlinevirtual

Minimize the makespan.

Definition at line 268 of file open-shop.cpp.

virtual void OpenShop::print ( std::ostream & os ) const

inlinevirtual

Print solution.

Reimplemented from Gecode::Driver::ScriptBase< BaseSpace >.

Definition at line 286 of file open-shop.cpp.

Friends And Related Function Documentation

const int ex0_p[]

 {
    661,6,333,
    168,489,343,
    171,505,324
  }

The instances.

Definition at line 346 of file open-shop.cpp.

const int ex1_p[]

 {
   54, 34, 61,  2,
    9, 15, 89, 70,
   38, 19, 28, 87,
   95, 34,  7, 29
  }

The instances.

Definition at line 353 of file open-shop.cpp.

const int ex2_p[]

 {
   5, 70, 45, 83,
   24, 80, 58, 45,
   29, 56, 29, 61,
   43, 64, 45, 74
  }

The instances.

Definition at line 361 of file open-shop.cpp.

const int ex3_p[]

 {
   89, 39, 54, 34, 71, 92, 56,
   19, 13, 81, 46, 91, 73, 27,
   66, 95, 48, 24, 96, 18, 14,
   48, 46, 78, 94, 19, 68, 63,
   60, 28, 91, 75, 52,  9,  7,
   33, 98, 37, 11,  2, 30, 38,
   83, 45, 37, 77, 52, 88, 52
  }

The instances.

Definition at line 369 of file open-shop.cpp.

const int ex4_p[]

 {
   49, 58, 37, 79, 16, 64, 71, 65, 6, 44, 17, 85, 99, 57, 89, 4, 16, 8, 40, 66,
   43, 65, 42, 35, 57, 3, 8, 65, 79, 76, 82, 80, 96, 82, 98, 57, 73, 43, 6, 20,
   82, 49, 7, 18, 94, 76, 41, 17, 43, 15, 53, 10, 83, 24, 79, 62, 53, 77, 23, 70,
   18, 30, 80, 7, 97, 84, 10, 27, 7, 91, 14, 12, 7, 31, 24, 97, 16, 33, 99, 15,
   31, 65, 51, 95, 45, 70, 57, 10, 84, 52, 28, 43, 54, 40, 83, 9, 21, 57, 45, 67,
   70, 45, 48, 39, 10, 37, 22, 53, 48, 50, 76, 48, 57, 6, 43, 13, 45, 93, 42, 11,
   80, 5, 53, 97, 75, 22, 10, 70, 79, 92, 96, 18, 57, 3, 82, 52, 1, 21, 23, 38,
   43, 79, 67, 57, 33, 52, 1, 44, 82, 10, 27, 23, 89, 9, 62, 6, 38, 33, 37, 22,
   68, 20, 5, 25, 16, 80, 13, 73, 35, 36, 13, 53, 97, 50, 17, 54, 35, 86, 24, 56,
   60, 83, 8, 81, 3, 4, 48, 14, 77, 10, 71, 57, 86, 94, 49, 36, 62, 62, 41, 56,
   31, 77, 5, 97, 19, 19, 31, 19, 26, 41, 77, 64, 74, 11, 98, 30, 22, 22, 33, 61,
   7, 89, 46, 13, 33, 55, 84, 16, 21, 45, 15, 71, 57, 42, 82, 13, 62, 98, 36, 45,
   84, 90, 20, 61, 24, 59, 8, 49, 53, 53, 83, 76, 28, 62, 59, 11, 41, 2, 58, 46,
   32, 23, 53, 5, 8, 91, 97, 53, 90, 90, 28, 16, 61, 27, 32, 74, 23, 11, 57, 20,
   62, 85, 79, 96, 62, 85, 43, 53, 12, 36, 95, 37, 2, 48, 46, 81, 97, 54, 5, 77,
   57, 35, 41, 55, 72, 98, 22, 81, 6, 8, 70, 64, 55, 53, 7, 38, 58, 30, 83, 81,
   15, 11, 24, 63, 27, 90, 35, 22, 53, 22, 66, 75, 59, 80, 31, 91, 63, 82, 99, 62,
   4, 18, 99, 6, 65, 21, 28, 93, 16, 26, 1, 16, 46, 59, 45, 90, 69, 76, 25, 53,
   50, 24, 66, 2, 17, 85, 5, 86, 4, 88, 44, 5, 29, 19, 27, 14, 36, 57, 59, 15,
   71, 79, 7, 61, 45, 72, 61, 45, 61, 54, 90, 33, 81, 5, 45, 64, 87, 82, 61, 8
  }

The instances.

Definition at line 380 of file open-shop.cpp.

OpenShopSpec examples[] = { ex0, ex1, ex2, ex3, ex4 }

Definition at line 405 of file open-shop.cpp.

const unsigned int n_examples = sizeof(examples) / sizeof(OpenShopSpec)

Definition at line 407 of file open-shop.cpp.

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 312 of file open-shop.cpp.

OpenShopSpec ex0	(	3	,
		3	,
		ex0_p
	)

OpenShopSpec ex1	(	4	,
		4	,
		ex1_p
	)

OpenShopSpec ex2	(	4	,
		4	,
		ex2_p
	)

OpenShopSpec ex3	(	7	,
		7	,
		ex3_p
	)

OpenShopSpec ex4	(	20	,
		20	,
		ex4_p
	)

Member Data Documentation

const OpenShopSpec& OpenShop::spec

protected

The instance specification.

Definition at line 71 of file open-shop.cpp.

BoolVarArray OpenShop::b

protected

Precedences.

Definition at line 73 of file open-shop.cpp.

IntVar OpenShop::makespan

protected

Makespan.

Definition at line 75 of file open-shop.cpp.

IntVarArray OpenShop::_start

protected

Start times.

Definition at line 77 of file open-shop.cpp.

The documentation for this class was generated from the following file:

examples/open-shop.cpp (Revision: 11473)

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Related Functions

Open shop specifications

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation