or-tools/examples/cpp/jobshop_ls.cc File Reference

#include <cstdio>
#include <cstdlib>
#include "base/commandlineflags.h"
#include "base/integral_types.h"
#include "base/logging.h"
#include "base/stringprintf.h"
#include "base/bitmap.h"
#include "constraint_solver/constraint_solver.h"
#include "constraint_solver/constraint_solveri.h"
#include "cpp/jobshop.h"

Go to the source code of this file.

Namespaces
namespace	operations_research
Classes
class	operations_research::SwapIntervals
	Exchange 2 intervals on a sequence variable. More...
class	operations_research::ShuffleIntervals
	Shuffle a fixed-length sub-sequence on one sequence variable. More...
class	operations_research::SequenceLns
	LNS Operator. More...
Functions
	DEFINE_string (data_file,"","Required: input file description the scheduling problem to solve, ""in our jssp format:\n"" - the first line is \"instance <instance name>\"\n"" - the second line is \"<number of jobs> <number of machines>\"\n"" - then one line per job, with a single space-separated ""list of \"<machine index> <duration>\"\n""note: jobs with one task are not supported")
	Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License.
	DEFINE_int32 (time_limit_in_ms, 60000,"Time limit in ms, 0 means no limit.")
	DEFINE_int32 (shuffle_length, 4,"Length of sub-sequences to shuffle LS.")
	DEFINE_int32 (sub_sequence_length, 4,"Length of sub-sequences to relax in LNS.")
	DEFINE_int32 (lns_seed, 1,"Seed of the LNS random search")
	DEFINE_int32 (lns_limit, 30,"Limit the size of the search tree in a LNS fragment")
void	operations_research::JobshopLs (const JobShopData &data)
	Model and Solve.
int	main (int argc, char **argv)
Variables
static const char	kUsage []
	namespace operations_research

---

Function Documentation

DEFINE_int32	(	lns_limit	,
		30	,
		"Limit the size of the search tree in a LNS fragment"
	)

DEFINE_int32	(	lns_seed	,
		1	,
		"Seed of the LNS random search"
	)

DEFINE_int32	(	sub_sequence_length	,
		4	,
		"Length of sub-sequences to relax in LNS."
	)

DEFINE_int32	(	shuffle_length	,
		4	,
		"Length of sub-sequences to shuffle LS."
	)

DEFINE_int32	(	time_limit_in_ms	,
		60000	,
		"Time limit in	ms,
		0 means no limit."
	)

DEFINE_string	(	data_file	,
		""	,
		"Required: input file description the scheduling problem to	solve,
		""in our jssp format:\n""-the first line is\"instance <instance name>\"\n"" - the second line is \"<number of jobs> <number of machines>\"\n"" - then one line per	job,
		with a single space-separated""list of\"<machine index> <duration>\"\n""note: jobs with one task are not supported"
	)

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License.

You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

This model implements a simple jobshop problem.

A jobshop is a standard scheduling problem where you must schedule a set of jobs on a set of machines. Each job is a sequence of tasks (a task can only start when the preceding task finished), each of which occupies a single specific machine during a specific duration. Therefore, a job is simply given by a sequence of pairs (machine id, duration). The objective is to minimize the 'makespan', which is the duration between the start of the first task (across all machines) and the completion of the last task (across all machines).

This will be modelled by sets of intervals variables (see class IntervalVar in constraint_solver/constraint_solver.h), one per task, representing the [start_time, end_time] of the task. Tasks in the same job will be linked by precedence constraints. Tasks on the same machine will be covered by Sequence constraints.

Search will be implemented as local search on the sequence variables.

int main	(	int	argc,
		char **	argv
	)

Definition at line 450 of file jobshop_ls.cc.

---

Variable Documentation

const char kUsage[] [static]

Initial value:

    "Usage: see flags.\nThis program runs a simple job shop optimization "
    "output besides the debug LOGs of the solver."

namespace operations_research

Definition at line 446 of file jobshop_ls.cc.