Detailed Description

scheduling problem file reader for RCPSP format

Author: Michael Bastubbe; Stefan Heinz

This reader is capabale of parsing resource-constrained project scheduling problem (RCPSP) instances. The PSPlib provides several instances set.

Definition in file reader_sm.c.

#include <ctype.h>
#include "heur_listscheduling.h"
#include "reader_sm.h"
#include "scip/cons_cumulative.h"
#include "scip/cons_linear.h"
#include "scip/cons_varbound.h"

Go to the source code of this file.

Macros
#define	READER_NAME "smreader"

#define	READER_DESC "scheduling file reader for sm files (RCPSP format)"

#define	READER_EXTENSION "sm"

#define	SM_MAX_LINELEN 65536

Default parameter values
#define	DEFAULT_FILENAME "-"

Typedefs
typedef enum reading_states	STATE

typedef struct SCIP_RcpspData	SCIP_RCPSPDATA

Enumerations
enum	reading_states { ERROR = 0 , NEXT , NJOBS , JOBS , NRESOURCES , RESOURCENAMES , RESOURCECAPACITIES , PRECEDENCES , END }

Functions
static void	parseError (SCIP scip, int lineno, const char msg, const char erritem, STATE state)

static void	checkForNewSection (char linestr, STATE state)

static SCIP_RETCODE	getNResources (SCIP scip, int lineno, char linestr, STATE state, SCIP_RCPSPDATA rcpspdata)

static SCIP_RETCODE	getNJobs (SCIP scip, int lineno, char linestr, STATE state, SCIP_RCPSPDATA rcpspdata)

static SCIP_RETCODE	getResourcesNames (SCIP scip, char linestr, STATE state, SCIP_RCPSPDATA rcpspdata)

static SCIP_RETCODE	getResourcesCapacities (SCIP scip, char linestr, STATE state, SCIP_RCPSPDATA rcpspdata)

static SCIP_RETCODE	getJobs (SCIP scip, char linestr, STATE state, SCIP_RCPSPDATA rcpspdata)

static SCIP_RETCODE	getPrecedence (SCIP scip, char s, STATE state, SCIP_RCPSPDATA rcpspdata)

static int	computeUbmakespan (int durations, int njobs, SCIP_DIGRAPH precedencegraph)

static SCIP_RETCODE	readFile (SCIP scip, const char filename, SCIP_RCPSPDATA *rcpspdata)

static	SCIP_DECL_READERCOPY (readerCopySm)

static	SCIP_DECL_READERREAD (readerReadSm)

SCIP_RETCODE	SCIPincludeReaderSm (SCIP *scip)

SCIP_RETCODE	SCIPcreateSchedulingProblem (SCIP scip, const char problemname, const char jobnames, const char resourcenames, int *demands, SCIP_DIGRAPH precedencegraph, int durations, int capacities, int njobs, int nresources, SCIP_Bool initialize)

Macro Definition Documentation

◆ READER_NAME

#define READER_NAME "smreader"

Definition at line 47 of file reader_sm.c.

◆ READER_DESC

#define READER_DESC "scheduling file reader for sm files (RCPSP format)"

Definition at line 48 of file reader_sm.c.

◆ READER_EXTENSION

#define READER_EXTENSION "sm"

Definition at line 49 of file reader_sm.c.

◆ DEFAULT_FILENAME

#define DEFAULT_FILENAME "-"

file name of precedence graph output file (in GML format), or - if no output should be created

Definition at line 57 of file reader_sm.c.

◆ SM_MAX_LINELEN

#define SM_MAX_LINELEN 65536

size of the line buffer for reading or writing

Definition at line 63 of file reader_sm.c.

Typedef Documentation

◆ STATE

typedef enum reading_states STATE

Definition at line 76 of file reader_sm.c.

◆ SCIP_RCPSPDATA

typedef struct SCIP_RcpspData SCIP_RCPSPDATA

Definition at line 91 of file reader_sm.c.

Enumeration Type Documentation

◆ reading_states

enum reading_states

Enumerator
ERROR
NEXT
NJOBS
JOBS
NRESOURCES
RESOURCENAMES
RESOURCECAPACITIES
PRECEDENCES
END

Definition at line 65 of file reader_sm.c.

Function Documentation

◆ parseError()

static void parseError	(	SCIP *	scip,
		int	lineno,
		const char *	msg,
		const char *	erritem,
		STATE *	state
	)

static

print error message

Parameters

scip	SCIP data structure
lineno	current line number of input file
msg	error message to display
erritem	token where the error occurred, or NULL
state	pointer to current reading state

Definition at line 149 of file reader_sm.c.

References ERROR, NULL, SCIP_VERBLEVEL_MINIMAL, and SCIPverbMessage().

Referenced by getNJobs(), getNResources(), and readFile().

◆ checkForNewSection()

static void checkForNewSection	(	char *	linestr,
		STATE *	state
	)

static

check if we reached a section

Parameters

linestr	current line
state	pointer to current reading state

Definition at line 174 of file reader_sm.c.

References JOBS, NJOBS, NRESOURCES, NULL, PRECEDENCES, and RESOURCENAMES.

Referenced by readFile().

◆ getNResources()

static SCIP_RETCODE getNResources	(	SCIP *	scip,
		int	lineno,
		char *	linestr,
		STATE *	state,
		SCIP_RCPSPDATA *	rcpspdata
	)

static

parese number of resources

Parameters

scip	SCIP data structure
lineno	current line number of input file
linestr	current line
state	pointer to current reading state
rcpspdata	pointer to resources constrained project scheduling data

Definition at line 196 of file reader_sm.c.

References NEXT, NULL, number, parseError(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPstrtok(), and SCIPstrToRealValue().

Referenced by readFile().

◆ getNJobs()

static SCIP_RETCODE getNJobs	(	SCIP *	scip,
		int	lineno,
		char *	linestr,
		STATE *	state,
		SCIP_RCPSPDATA *	rcpspdata
	)

static

parse number of jobs

Parameters

scip	SCIP data structure
lineno	current line number of input file
linestr	current line
state	pointer to current reading state
rcpspdata	pointer to resources constrained project scheduling data

Definition at line 236 of file reader_sm.c.

References NEXT, NULL, number, parseError(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPstrtok(), and SCIPstrToRealValue().

Referenced by readFile().

◆ getResourcesNames()

static SCIP_RETCODE getResourcesNames	(	SCIP *	scip,
		char *	linestr,
		STATE *	state,
		SCIP_RCPSPDATA *	rcpspdata
	)

static

pares resource capacities

Parameters

scip	SCIP data structure
linestr	current line
state	pointer to current reading state
rcpspdata	pointer to resources constrained project scheduling data

Definition at line 274 of file reader_sm.c.

References NULL, r, RESOURCECAPACITIES, SCIP_CALL, SCIP_OKAY, SCIPduplicateBufferArray, and SCIPstrtok().

Referenced by readFile().

◆ getResourcesCapacities()

static SCIP_RETCODE getResourcesCapacities	(	SCIP *	scip,
		char *	linestr,
		STATE *	state,
		SCIP_RCPSPDATA *	rcpspdata
	)

static

parse resource capacities

Parameters

scip	SCIP data structure
linestr	current line
state	pointer to current reading state
rcpspdata	pointer to resources constrained project scheduling data

Definition at line 312 of file reader_sm.c.

References END, NULL, r, SCIP_OKAY, SCIP_Real, and SCIPstrToRealValue().

Referenced by readFile().

◆ getJobs()

static SCIP_RETCODE getJobs	(	SCIP *	scip,
		char *	linestr,
		STATE *	state,
		SCIP_RCPSPDATA *	rcpspdata
	)

static

parese job informations

Parameters

scip	SCIP data structure
linestr	current line
state	pointer to current reading state
rcpspdata	pointer to resources constrained project scheduling data

Definition at line 339 of file reader_sm.c.

References JOBS, NEXT, NULL, r, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_READERROR, SCIPallocBufferArray, SCIPduplicateBufferArray, SCIPsnprintf(), and SCIPstrToIntValue().

Referenced by readFile().

◆ getPrecedence()

static SCIP_RETCODE getPrecedence	(	SCIP *	scip,
		char *	s,
		STATE *	state,
		SCIP_RCPSPDATA *	rcpspdata
	)

static

get precedence relationship

Parameters

scip	SCIP data structure
s	current line
state	pointer to current reading state
rcpspdata	pointer to resources constrained project scheduling data

Definition at line 403 of file reader_sm.c.

References NEXT, NULL, PRECEDENCES, SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIPcreateDigraph(), SCIPdigraphAddArc(), and SCIPstrToIntValue().

Referenced by readFile().

◆ computeUbmakespan()

static int computeUbmakespan	(	int *	durations,
		int	njobs,
		SCIP_DIGRAPH *	precedencegraph
	)

static

compute trivial upper bound for makespan

Parameters

durations	array of durations
njobs	number og jobs
precedencegraph	direct graph to store the precedence conditions

Definition at line 466 of file reader_sm.c.

References MAX, SCIPdigraphGetNSuccessors(), and SCIPdigraphGetSuccessorsData().

Referenced by SCIPcreateSchedulingProblem().

◆ readFile()

static SCIP_RETCODE readFile	(	SCIP *	scip,
		const char *	filename,
		SCIP_RCPSPDATA *	rcpspdata
	)

static

read file

Parameters

scip	SCIP data structure
filename	name of input file
rcpspdata	pointer to resources constrained project scheduling data

Definition at line 507 of file reader_sm.c.

References checkForNewSection(), END, ERROR, getJobs(), getNJobs(), getNResources(), getPrecedence(), getResourcesCapacities(), getResourcesNames(), JOBS, NEXT, NJOBS, NRESOURCES, NULL, parseError(), PRECEDENCES, RESOURCECAPACITIES, RESOURCENAMES, SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIPABORT, SCIPdebugMessage, SCIPerrorMessage, SCIPfclose(), SCIPfgets(), SCIPfopen(), and SM_MAX_LINELEN.

Referenced by SCIP_DECL_READERREAD().

◆ SCIP_DECL_READERCOPY()

static SCIP_DECL_READERCOPY ( readerCopySm )

static

copy method for reader plugins (called when SCIP copies plugins)

Definition at line 615 of file reader_sm.c.

References NULL, READER_NAME, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_STRINGEQ, SCIPincludeReaderSm(), and SCIPreaderGetName().

◆ SCIP_DECL_READERREAD()

static SCIP_DECL_READERREAD ( readerReadSm )

static

problem reading method of reader

Definition at line 630 of file reader_sm.c.

References NULL, r, READER_NAME, readFile(), SCIP_CALL, SCIP_FILECREATEERROR, SCIP_OKAY, SCIP_SUCCESS, SCIPcreateSchedulingProblem(), SCIPdebug, SCIPdigraphFree(), SCIPdigraphPrintGml(), SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetStringParam(), SCIPprintSysError(), and TRUE.

◆ SCIPincludeReaderSm()

SCIP_RETCODE SCIPincludeReaderSm ( SCIP * scip )

includes the sch file reader in SCIP

Parameters

scip	SCIP data structure

Definition at line 715 of file reader_sm.c.

References DEFAULT_FILENAME, FALSE, NULL, READER_DESC, READER_EXTENSION, READER_NAME, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddStringParam(), SCIPincludeReaderBasic(), SCIPsetReaderCopy(), and SCIPsetReaderRead().

Referenced by runShell(), and SCIP_DECL_READERCOPY().

◆ SCIPcreateSchedulingProblem()

SCIP_RETCODE SCIPcreateSchedulingProblem	(	SCIP *	scip,
		const char *	problemname,
		const char **	jobnames,
		const char **	resourcenames,
		int **	demands,
		SCIP_DIGRAPH *	precedencegraph,
		int *	durations,
		int *	capacities,
		int	njobs,
		int	nresources,
		SCIP_Bool	initialize
	)

creates a cumulative scheduling problem

Parameters

scip	SCIP data structure
problemname	problem name
jobnames	job names, or NULL
resourcenames	resource names, or NULL
demands	demand matrix resource job demand
precedencegraph	direct graph to store the precedence conditions
durations	array to store the processing for each job
capacities	array to store the different capacities
njobs	number of jobs to be parsed
nresources	number of capacities to be parsed
initialize	initialize list scheduling heuristic

Definition at line 746 of file reader_sm.c.

References computeUbmakespan(), FALSE, NULL, r, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_INTEGER, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPcreateConsCumulative(), SCIPcreateConsVarbound(), SCIPcreateProb(), SCIPcreateVar(), SCIPdebugMessage, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphGetSuccessorsData(), SCIPfreeBufferArray, SCIPinfinity(), SCIPinitializeHeurListScheduling(), SCIPmarkDoNotMultaggrVar(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), and TRUE.

Referenced by readFile(), and SCIP_DECL_READERREAD().

SCIP

Detailed Description

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ READER_NAME

◆ READER_DESC

◆ READER_EXTENSION

◆ DEFAULT_FILENAME

◆ SM_MAX_LINELEN

Typedef Documentation

◆ STATE

◆ SCIP_RCPSPDATA

Enumeration Type Documentation

◆ reading_states

Function Documentation

◆ parseError()

◆ checkForNewSection()

◆ getNResources()

◆ getNJobs()

◆ getResourcesNames()

◆ getResourcesCapacities()

◆ getJobs()

◆ getPrecedence()

◆ computeUbmakespan()

◆ readFile()

◆ SCIP_DECL_READERCOPY()

◆ SCIP_DECL_READERREAD()

◆ SCIPincludeReaderSm()

◆ SCIPcreateSchedulingProblem()