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 <assert.h>
#include <string.h>
#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 "-"

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 49 of file reader_sm.c.

◆ READER_DESC

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

Definition at line 50 of file reader_sm.c.

◆ READER_EXTENSION

#define READER_EXTENSION "sm"

Definition at line 51 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 59 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 65 of file reader_sm.c.

Referenced by readFile().

Typedef Documentation

◆ STATE

typedef enum reading_states STATE

Definition at line 78 of file reader_sm.c.

◆ SCIP_RCPSPDATA

typedef struct SCIP_RcpspData SCIP_RCPSPDATA

Definition at line 93 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 67 of file reader_sm.c.

Function Documentation

◆ parseError()

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 occured, or NULL
state	pointer to current reading state

Definition at line 151 of file reader_sm.c.

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

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

◆ checkForNewSection()

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 176 of file reader_sm.c.

References assert(), JOBS, NJOBS, NRESOURCES, NULL, PRECEDENCES, and RESOURCENAMES.

Referenced by readFile().

◆ getNResources()

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 198 of file reader_sm.c.

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

Referenced by readFile().

◆ getNJobs()

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 238 of file reader_sm.c.

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

Referenced by readFile().

◆ getResourcesNames()

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 276 of file reader_sm.c.

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

Referenced by readFile().

◆ getResourcesCapacities()

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 314 of file reader_sm.c.

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

Referenced by readFile().

◆ getJobs()

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 341 of file reader_sm.c.

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

Referenced by readFile().

◆ getPrecedence()

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 405 of file reader_sm.c.

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

Referenced by readFile().

◆ computeUbmakespan()

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 468 of file reader_sm.c.

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

Referenced by SCIPcreateSchedulingProblem().

◆ readFile()

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 509 of file reader_sm.c.

References assert(), 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()

SCIP_DECL_READERCOPY ( readerCopySm )

static

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

Definition at line 617 of file reader_sm.c.

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

◆ SCIP_DECL_READERREAD()

SCIP_DECL_READERREAD ( readerReadSm )

static

problem reading method of reader

Definition at line 631 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 716 of file reader_sm.c.

References assert(), 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 747 of file reader_sm.c.

References assert(), computeUbmakespan(), FALSE, i, NULL, nvars, r, SCIP_Bool, 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(), TRUE, var, and vars.

Referenced by readFile(), readFile(), and SCIP_DECL_READERREAD().

Detailed Description

Macros

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()