Skip to content

List of scheduling environments

Jump to bottom
Jose M Framiñán edited this page Sep 15, 2022 · 21 revisions

Introduction

In the next sections, the scheduling models (layouts) currently implemented in scheptk is listed. The creation and usage of customised scheduling models is discussed here.

Single Machine

This class serves to model a single machine scheduling problem, where a set of jobs have to be processed on a single machine. This is the Gantt chart produced with the instance in the file and the solution procedure in the sample.

Atrributes

Some of the attributes are mandatory and produce an error if not found when loading the instance file. Others are optional, but they may produce errors in some cases if missing (e.g. if due dates are ommitted, then due-date related criteria cannot be computed).

  • Mandatory:
  • jobs - number of jobs
  • pt - processing times (a list containing the processing time of each job)
  • Optional:
  • w - weights. The weight of each job. If not specified, they are assumed to be 1.0
  • r - release dates. The earliest starting time of each job. If not specified, they are assumed to be 0
  • dd - due dates. The due date of each job. If not specified, they are assumed to be infinite

Instance

A typical instance is the following:

[PT=2,10,1,1]
[DD=11,13,13,14]
[W=2.0,1,1,2]
[R=0,0,0,0]
[JOBS=4]

Solution encoding

A semiactive (no idle) schedule for a single machine typically consists of providing an order (sequence) in which the jobs are processed in the machine, i.e.

solution = [3,2,0,1]

Sample code

from scheptk.scheptk import SingleMachine

instance = SingleMachine('test_single.txt')
solution = [3,2,0,1]
print('Max. tardiness is {}'.format(instance.Tmax(solution)))
instance.print_schedule(solution, '..\\documentation\\images\\single_sample.png')

Parallel Machines

This class serves to model a (identical) parallel machine scheduling problem. Each job has to be processed in one machine. This is the Gantt chart produced with the instance in the sample and the solution in the solution encoding section.

Atrributes

Some of the attributes are mandatory and produce an error if not found when loading the instance file. Others are optional, but they may produce errors in some cases if missing (e.g. if due dates are ommitted, then due-date related criteria cannot be computed).

  • Mandatory:
  • jobs - number of jobs
  • pt - processing times (a list containing the processing time of each job), which is the same in all machines
  • Optional:
  • w - weights. The weight of each job. If not specified, they are assumed to be 1.0
  • r - release dates. The earliest starting time of each job. If not specified, they are assumed to be 0
  • dd - due dates. The due date of each job. If not specified, they are assumed to be infinite

Instance

A typical instance is the following:

[PT=2,10,4,5,7,9,1,8]
[JOBS=8]
[MACHINES=3]

Solution encoding

There are several possibilites for encoding a solution. Perhaps the easiest is to provide an order (sequence) in which the jobs enter the system and assign the job to the machine according to the ECT (Earliest Completion Time) rule, i.e. the job is allocated to the machine that finishes first. Ties are broken according to the index of the machine, so machines with lower index have higher priority for the allocation.

solution = [1, 5, 6, 2, 3, 4, 7, 0]

Sample code

Unrelated machines

This class serves to model parallel, but not identical machines. Each job has to be processed in one of these machines, but the processing times are machine-dependent. This is the Gantt chart produced with the instance in the sample and the solution in the solution encoding section.

Atrributes

Some of the attributes are mandatory and produce an error if not found when loading the instance file. Others are optional, but they may produce errors in some cases if missing (e.g. if due dates are ommitted, then due-date related criteria cannot be computed).

  • Mandatory:
  • jobs - number of jobs
  • pt - processing times of each job on each machine. It is a list of lists, i.e. a list containing the processing times of all jobs on the machine, so instance.pt[i][j] indicates the processing times of job j on machine i.
  • Optional:
  • w - weights. The weight of each job. If not specified, they are assumed to be 1.0
  • r - release dates. The earliest starting time of each job. If not specified, they are assumed to be 0
  • dd - due dates. The due date of each job. If not specified, they are assumed to be infinite

Instance

A typical instance is the following:

[JOBS=6]
[MACHINES=2]
[PT=5,13,5,2,8,6;9,12,10,4,3,10]

Solution encoding

There are several possibilites for encoding a solution. Perhaps the easiest is to provide an order (sequence) in which the jobs enter the system and assign the job to the machine according to the ECT (Earliest Completion Time) rule, i.e. the job is allocated to the machine that would first complete this job. Ties are broken according to the index of the machine, so machines with lower index have higher priority for the allocation.

solution = [5, 1, 4, 2, 3, 0]

Sample code

from scheptk.scheptk import UnrelatedMachines
instancia = UnrelatedMachines('test_unrelated.txt')
sequence = [5, 1, 4, 2, 3, 0]
print(sequence)

Flow Shop

This class serves to model the permutation flowshop scheduling problem. Each job has to be processed in all machines in the same order. This is the Gantt chart produced with the instance in the sample and the solution in the solution encoding section.

Atrributes

Some of the attributes are mandatory and produce an error if not found when loading the instance file. Others are optional, but they may produce errors in some cases if missing (e.g. if due dates are ommitted, then due-date related criteria cannot be computed).

  • Mandatory:
  • jobs - number of jobs
  • pt - processing times of each job on each machine. It is a list of lists, i.e. a list containing the processing times of all jobs on the machine, so instance.pt[i][j] indicates the processing times of job j on machine i.
  • Optional:
  • w - weights. The weight of each job. If not specified, they are assumed to be 1.0
  • r - release dates. The earliest starting time of each job. If not specified, they are assumed to be 0
  • dd - due dates. The due date of each job. If not specified, they are assumed to be infinite

Instance

A typical instance is the following:

[JOBS=6]
[MACHINES=2]
[PT=5,13,5,2,8,6;9,12,10,4,3,10]

Solution encoding

A sequence indicating the order in which the jobs are going to be processed in all machines.

solution = [0,1,4,3,2]

Sample code

from scheptk.scheptk import FlowShop
instance = FlowShop('test_flowshop.txt')
sequence = [0,1,4,3,2]
instance.print_schedule(sequence)

makespan = instance.Cmax(sequence)

Job Shop

This class serves to model the jobshop scheduling problem. Each job has to be processed in all machines in an order given by a routing matrix. This is the Gantt chart produced with the instance in the sample and the solution in the solution encoding section.

Atrributes

Some of the attributes are mandatory and produce an error if not found when loading the instance file. Others are optional, but they may produce errors in some cases if missing (e.g. if due dates are ommitted, then due-date related criteria cannot be computed).

  • Mandatory:
  • jobs - number of jobs
  • pt - processing times of each job on each machine. It is a list of lists, i.e. a list containing the processing times of all jobs on the machine, so instance.pt[i][j] indicates the processing times of job j on machine i.
  • rt - routing matrix. It is a list of lists, i.e. a list containing the routing of each jobs across the machines, so instance.rt[j] indicates the routing of job j, i.e. a list of the machines to be visited by the job so instance.rt[j][i] indicates the machine to be visited by job j in the i-th order.
  • Optional:
  • w - weights. The weight of each job. If not specified, they are assumed to be 1.0
  • r - release dates. The earliest starting time of each job. If not specified, they are assumed to be 0
  • dd - due dates. The due date of each job. If not specified, they are assumed to be infinite

Instance

A typical instance is the following:

[JOBS=5]
[MACHINES=4]
[PT=31,19,23,13,33;41,55,42,22,5;25,3,27,14,57;30,34,6,13,19]
[RT=0,1,2,3;3,1,0,2;2,0,1,3;1,3,2,0;3,0,2,1]
[DD=300,0,0,0,0]
[R=0,0,0,0,0]

Solution encoding

There are several possibilites for encoding a solution in a Job Shop. Perhaps the easiest is to provide an extended sequence where the jobs iteratively are assigned to the corresponding machine in their routing. solution =[4, 4, 3, 1, 1, 3, 1, 4, 1, 3, 2, 0, 4, 2, 2, 2, 0, 0, 0, 3] indicates that first job 4 is assigned to its first machine in its routing matrix, then job 4 is assigned to its second machine, then job 3 is assigned to its first machine, etc.

Sample code

from scheptk.scheptk import JobShop


instance = JobShop('test_jobshop.txt')
sol = [4, 4, 3, 1, 1, 3, 1, 4, 1, 3, 2, 0, 4, 2, 2, 2, 0, 0, 0, 3]
print(sol)
print('Cmax={}'.format(instance.Cmax(sol)))
print('SumCj={}'.format(instance.SumCj(sol)))
instance.write_schedule(sol, 'jobshop.sch')
instance.print_schedule(sol, '..\\documentation\\images\\jobshop_sample.png')

Open Shop

This class serves to model the open shop scheduling problem. Each job has to be processed in all machines in any order (no routing matrix). This is the Gantt chart produced with the instance in the sample and the solution in the solution encoding section.

Atrributes

Some of the attributes are mandatory and produce an error if not found when loading the instance file. Others are optional, but they may produce errors in some cases if missing (e.g. if due dates are ommitted, then due-date related criteria cannot be computed).

  • Mandatory:
  • jobs - number of jobs
  • pt - processing times of each job on each machine. It is a list of lists, i.e. a list containing the processing times of all jobs on the machine, so instance.pt[i][j] indicates the processing times of job j on machine i.
  • Optional:
  • w - weights. The weight of each job. If not specified, they are assumed to be 1.0
  • r - release dates. The earliest starting time of each job. If not specified, they are assumed to be 0
  • dd - due dates. The due date of each job. If not specified, they are assumed to be infinite

Instance

A typical instance is the following:

[JOBS=3]
[MACHINES=3]
[PT=10,5,18;15,20,6;10,16,8]

Solution encoding

Here it is used the so-called operations sequence solution encoding. Here it is an example of such encoding for a 3 job, 3 machine open shop instance:

Operation 0 1 2 3 4 5 6 7 8
Machine 0 0 0 1 1 1 2 2 2
Job 0 1 2 0 1 2 0 1 2

Therefore sol=[7,5,4,0,1,6,3,2,8] indicates that job 1 is first processed on machine 2, then job 2 is processed on machine 1, next job 1 is processed on machine 1, job 0 on machine 0 and so forth.

Sample code

from scheptk.scheptk import OpenShop

instance = OpenShop('test_openshop.txt')
sol = [7,5,4,0,1,6,3,2,8]
print(sol)
print("Cmax={}".format(instance.Cmax(sol)))
instance.write_schedule(sol, 'openshop.sch')

Table of contents

Clone this wiki locally