allfiles

Overview

The models provided in scheptk are canonical models that do not include many constraints and objectives that may be found in real-life (such as setups, precedence constraints, or non-regular objectives). There are several functionalities in scheptk that allow you to create customised models with minimal effort, as well as solution procedures for these models.

In a nutshell, customised models are children of the Model class that carry out certain scheduling functions (e.g. which data to store and handle, how to compute the completion times, etc.) in an specific manner. So, in order to create a customised class, we should define the class as a children of the Model class and tell it how these specific funcions are carried out in this model.

Once these methods are described for the children class, all functions of scheptk should be available for the class. The following code summarises how a class Assembly_2_machines can be defined and used.

from scheptk.scheptk import Model
from scheptk.util import *

class Assembly_2_machines(Model):

    # constructor of the class: define the data (temporary=attributes, persistent=tags in the file)
    def __init__(self, filename):

        self.jobs = read_tag(filename,'JOBS')
        self.pt = read_tag(filename,'PT')


    # computes the completion time of each job on each machine
    def ct(self, solution):

        # completion time of jobs on each machine (the two first machines are the first stage, the third is the assembly stage)
        ct = [[0 for j in range(self.jobs)] for i in range(3)]

        # earliest starting time on the machines (initially zero)
        earliest_st_machine_1 = 0
        earliest_st_machine_2 = 0
        earliest_st_assembly = 0

        for j,job in enumerate(solution):

            # compute completion times of each job in the first stage
            ct[0][j] = earliest_st_machine_1 + self.pt[0][job] 
            ct[1][j] = earliest_st_machine_2 + self.pt[1][job] 
            
            # compute completion time of each job in the assembly stage
            ct[2][j] = max(earliest_st_assembly, max(ct[0][j], ct[1][j])) + self.pt[2][job]
            
            # update earliest completion times of the machines in the stages
            earliest_st_machine_1 = ct[0][j] 
            earliest_st_machine_2 = ct[1][j] 
            earliest_st_assembly = ct[2][j]
        
        return ct, solution

Once this code has been entered, all functions of a scheduling model in scheptk are available, i.e.:

instance = Assembly_2_machines('assembly_sample.txt')

solution = [1,0,2]
instance.Cmax(solution)
instance.SumCj(solution)
instance.print_schedule(solution)

and the makespan, the sum of the completion times, or even the Gantt chart can be depicted. In the next sections, the details of this code are provided.

The `Model` class

Roughly speaking, a scheduling model is an abstraction of a real-life scheduling problem where the decision problem can be modelled using a set of data, constraints, and objectives (criteria). Data in a scheduling model can be stored in a persistent manner (i.e. a file or a database), or loaded in the computer memory while running the program (i.e. variables, or the attributes of a model class). Constraints in a scheduling model usually determine how the jobs are processed in the machines, therefore are implemented as methods of the model class. These constraints determine the value of certain magnitudes of interest (criteria), so the objectives are also methods of the class.

The Model class is the parent class of all scheduling models in scheptk. All scheduling models (e.g. SingleMachine, JobShop) are children classes of Model. Model already implements a lot of methods that are model-independent once we define which input data requires our model and how these data are going to be used to compute the completion times. Therefore, to create a customised scheduling model we only need to create a children class of Model (so all generic methods for Model are inherited and can be used in the customised model), and specify in this children class the two following methods:

__init__(filename). This is the constructor of the class, so each time an instance of the class is created, it executes this method. We will use this constructor to specify a filename with a set of corresponding tags that weill be stored into attributes of the class (for instance, the file may contain a tag named JOBS that will be loaded into an attribute named jobs). The rules to write the constructor are described in detail here.
ct(solution). In this method it is specified the manner in which the completion times for the jobs in a solution are computed on each machine. This is clearly model-dependent (it is not the same e.g. in a standard flowshop than in a no-idle flowshop), so it has to be specifically written for the customised model. The rules to write ct are described in detail here.

Implementing a constructor for the customised model

As it has been mentioned above, __init__(filename) is the constructor where the data of the model are defined. Basically, in this function we will define what attributes would have the customised model, and what is the tag name that we will use to read them from a file. Typically, the __init(filename)__ will contain lines of code like the following one: self.attr= read_tag(filename,attr_tag) where attr is the name of the attribute (such as jobs, machines, setups, etc) and attr_tag is the corresponding tag in the file (such as 'JOBS', 'MACHINES', 'SETUPS', etc). In the example of the Assembly_2_machines class, the input file would read something like:

[JOBS=3]
[PT=40,4,8;21,14,25;16,5,12]

would require the following __init__(filename) method:

   def __init__(self, filename):

        self.jobs = read_tag(filename,'JOBS')
        self.pt = read_tag(filename,'PT')

Note that different tags could have been used for the model, for instance an input file like this:

[JOBS=3]
[PT_MACHINE_1=40,4,8]
[PT_MACHINE_2=21,14,25]
[PT_ASSEMBLY=16,5,12]

and the corresponding __init__(filename) method would be

   def __init__(self, filename):

        self.jobs = read_tag(filename,'JOBS')
        self.pt = [read_tag(filename,'PT_MACHINE_1'), read_tag(filename,'PT_MACHINE_2'), read_tag(filename,'PT_ASSEMBLY')]

which is certainly more visual although less simple. In any case, it is very important that the attribute processing times are stored in the standard way, i.e. self.pt[i][j] is a list containing, for each machine, the processing time of each job on this machine, or (in the case of a single machine) self.pt[j] is a list containing the processing time of each job. If this structure for the processing times is not followed, then it is likely that the functionalities related to the Gantt charts do not work properly. In this case, however, it is always possible to use the class Schedule to produce an ad-hoc chart as described here.

Implementing a method to compute the completion times

It is known from an earlier section that ct(solution) is a method that takes a solution (in a user-defined solution encoding) and returns the completion time of each job in the solution on each machine and the order in which the jobs are specified in ct. To lliustrate this, the code for the ct() method in the single machine case is included:

    def ct(self,sequence):
        completion_time = []
        completion_time.append(self.r[sequence[0]] + self.pt[sequence[0]])
        for i in range(1,len(sequence)):
            completion_time.append(max(completion_time[i-1],self.r[sequence[i]]) + self.pt[sequence[i]])
        return [completion_time], sequence

It is important to remark that ct() returns a matrix (a list of lists) with as many rows as the number of machines, and as many columns as the number of jobs in the solution (not the total number of jobs). This difference is important for instance when one wants to deal with partial sequences (which represent partial solutions in many problems) and not with full sequences. This can be illustrated by the following example in the SingleMachine layout using the same 4-jobs instance that has been used to illustrate SingleMachine in another section of the wiki:

instance = SingleMachine('test_single.txt')
solution = [3,1]
completion_times, order_ct = instance.ct(solution)
print( 'Completion times: , completion_times )
print( 'Order of the jobs in the partial solution:', order_ct )

The execution of this code provides the following output:


----- Reading SingleMachine instance data from file test_single.txt -------
[JOBS=4]
[PT=2,10,1,1]
[W=2.0,1,1,2]
[DD=11,13,13,14]
[R=0,0,0,0]
----- end of SingleMachine instance data from file test_single.txt -------
Completion times: [[1, 11]]
Order of the jobs in the partial solution: [3, 1]

As it can be seen, the completion_time list returned is composed of one element (one machine, a row), in turn composed of two elements (two jobs, the columns). It is not a one machine, four jobs matrix even if in the instance there are 4 jobs. Failing to return the completion times in this way might result in problems when calculating the indicators of partial measures.

A sensible question at this point is, Why the order of the jobs has to be returned by the function? Is not this information already known? This discussion is been addressed in detail here, and the answer is, in general, no, as there are encoding schemes (such as the codification used by JobShop or OpenShop) where the solution provided to ct() is not the sequence or order of the jobs. However, this is not the case if the solution encoding is simply the sequence of the jobs. However, since the methods related to Gantt charts are defined at the parent level (the Model class), then ct() has to be written always in the same way regardless the layout.

In the following we can see another example of the method ct() for the case of UnrelatedMachines:


   # implementation of completion times for unrelated parallel machines (ECT rule)
    # ties are broken with the lowest index
   def ct(self, sequence):

        # initializing completion times in the machines to zero
        ct_machines = [0 for i in range(self.machines)]
        ct = [[0 for j in range(len(sequence))] for i in range(self.machines)]

        # assign all jobs
        for j in range(len(sequence)):
            # construct what completion times would be if the job is assigned to each machine
            next_ct = [max(ct_machines[i],self.r[sequence[j]]) + self.pt[i][sequence[j]] for i in range(self.machines)]
            # assign the job to the machine finishing first
            index_machine = find_index_min(next_ct)
            # increases the completion time of the corresponding machine (and sets the completion time of the job)
            ct_machines[index_machine] = max(ct_machines[index_machine], self.r[sequence[j]]) + self.pt[index_machine][sequence[j]]
            ct[index_machine][j] = ct_machines[index_machine]
    
        return ct, sequence

As it can be seen, the completion times returned include some zeros if the job is not processed in this machine. This is not a problem at all. Finally, please check the example of ct() for the JobShop() where it can be seen that the solution passed as argument is not the same thing that the list of the jobs:

     def ct(self, solution):
         
       # get the jobs involved in the solution in the order they are processed
       jobs_involved = list(set(solution))

       # completion times of jobs and machines
       ct_jobs = [self.r[jobs_involved[j]] for j in range(len(jobs_involved))]
       ct_machines = [0 for i in range(self.machines)]  

       # completion time of each job on each machine
       ct = [[0 for j in range(len(jobs_involved))] for i in range(self.machines)]

       # number of operations completed by each job (initially zero)
       n_ops_jobs = [0 for j in range(len(jobs_involved))]

       for job in solution:

           # determine the corresponding machine
           machine = self.rt[job][n_ops_jobs[jobs_involved.index(job)]]

           # compute completion time
           curr_completion_time = max(ct_jobs[jobs_involved.index(job)], ct_machines[machine]) + self.pt[machine][job]

           # update completion times
           ct_jobs[jobs_involved.index(job)] = curr_completion_time
           ct_machines[machine] = curr_completion_time
           ct[machine][jobs_involved.index(job)] = curr_completion_time

           # update number of operations for the job
           n_ops_jobs[jobs_involved.index(job)] += 1

       return ct, jobs_involved

```# Overview

`scheptk` includes the class `Schedule`, which can be used to save, load and print schedules that can be generated by the supporting scheduling layouts, or can be also generated autonomously by adding tasks to an existing schedule.

A typical schedule file is a text file containing the following tags:

[JOBS=5] [MACHINES=4] [SCHEDULE_DATA=1,0,10,0,10,10;1,10,20,2,40,20;2,80,120;1,30,10;3,30,10] [JOB_ORDER=0,1,2,3,4]


The tag `JOBS` indicates the number of jobs in the schedule, `MACHINES` the number of machines, and `SCHEDULE_DATA` contains the tasks for each job (in the order given by `JOB_ORDER`) in the form of a tuple `machine, starting_time, duration`.

Different methods can be used to handle schedules. These are described in the next subsections



## Opening a schedule 

A schedule stored in a file `sched.sch` can be open using the constructor of the class `Schedule`. If no argument is specified, an empty instance of the `Schedule` class is created. The following code opens and print the schedule contained in the file `openshop.sch`

from scheptk.scheptk import Schedule

sched = Schedule('openshop.sch') sched.print()


## Saving a schedule

If the schedule has been generated autonomously, or is contained in an instance of the class `Schedule`, it can be saved using `save(filename)`.

from scheptk.scheptk import Schedule, Task

gantt = Schedule()

gantt.add_task(Task(0,0,10,20)) gantt.add_task(Task(0,1,0,10)) gantt.add_task(Task(1,1,10,30)) gantt.add_task(Task(1,2,40,60))

gantt.save('resulting_schedule.sched')



A schedule obtained from a given `instance` using a solution `sol`, it can be saved using the method `write_schedule(sol, filename)`.

from scheptk.scheptk import OpenShop

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


Alternatively, the method `create_schedule(solution)` can be used to get the corresponding schedule and then saving it using the `save()` method of the class `Schedule` as seen before.

from scheptk.scheptk import OpenShop

instance = OpenShop('test_openshop.txt') sol = [7,5,4,0,1,6,3,2,8] gantt = instance.create_schedule(sol) gantt.save('openshop.sch')




## Printing a schedule

Use the method `print()` in the class schedule. A filename to store the image can be specified optionally:

from scheptk.scheptk import Schedule, Task

gantt = Schedule()

gantt.add_task(Task(0,0,10,20)) gantt.add_task(Task(0,1,0,10)) gantt.add_task(Task(1,1,10,30)) gantt.add_task(Task(1,2,40,60))

gantt.print()



If the schedule is to be generated from a `solution` in a given layout, you can use the method `print_schedule(solution)` of the corresponding layout

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


The following image is printed:


[[/images/flowshop_sample.png]]

Alternatively, use `create_schedule()` to first obtain the schedule and later print it with the `print()` method, i.e.

from scheptk.scheptk import FlowShop instance = FlowShop("test_flowshop.txt") sequence = [0,1,4,3,2] gantt = instance.create_schedule(sequence) gantt.print('flowshop_sample.png')



# Creating a model-independent schedule

A schedule can be created by adding tasks to an instance of the class `Schedule`. The tasks are added using the method `add_task()`, which takes as argument an instance of the class `Task`. The constructor of the class `Task` requires four arguments, i.e. `Task(job, machine, st, ct)` where `job` and `machine` indicates the job and the machine whereas `st` and `ct` indicate the starting and completion times of the task, respectively. The following code creates an empty schedule, then it populates it with several tasks and finally prints the resulting schedule:

from scheptk.scheptk import Schedule, Task

gantt = Schedule()

gantt.add_task(Task(0,0,10,20)) gantt.add_task(Task(0,1,0,10)) gantt.add_task(Task(1,1,10,30)) gantt.add_task(Task(1,2,40,60)) gantt.add_task(Task(2,2,80,200)) gantt.add_task(Task(3,1,30,40)) gantt.add_task(Task(4,3,30,40))

gantt.print('figure.png')


The schedule generated is the following:

[[/images/sched_aut.png]]

# Printing Schedules of Customised Models

In general, a `Schedule` shows a Gantt chart with the evolution of the state of the machines in the layout over the time. There are three basic states for a machine in a given time:

- The machine may be busy while processing a job. This time period is denoted as a `Task` for the machine.
- The machine may be idle as there are no available jobs to be processed. This time period is represented in the Gantt chart by a void.
- The machine may be unavailable for processing a job (even if the job is available) as a set-up operation, maintenance process, breakdown, or another incidence makes the machine unavailable. This time period is denoted as `NAP`  (Non Availabiliy Period) :-)


[[/images/SingleMachineSetUp_NAP_sample.png]]

In the figure we can see the three periods in a `SingleMachine` layout. From period 0 to 10 the machine is idle (in this case it is because the job has a release date of 10 units). From period 10 to 48 the machine is processing J2. From period 48 to 73 there is a setup of 25 time units in order to prepare the tool from J2 to J0, and from time 73 to 93, job 0 is processed.

These elements can be implemented in `scheptk` adding to an existing `Schedule` object elements from the classes `Task` and `NAP`. In most cases, both objects are only using to give information to the schedule about the task and the NAP. The following line

new_task = Task(job_index, machine_index, st, ct)


creates a new task (named `new_task`) that processes job `job_index` on machine `machine_index` from time `st` to time `ct`. Analogously, the following line

new_nap = NAP(machine_index, st, ct, nap_tag)


creates a new NAP (named `new_nap`) where the machine `machine_index` is not available from time `st` to time `ct`. Optionally, the tag `nap_tag` will be set in this NAP when printing the Gantt diagram. The following complete code

from scheptk.scheptk import Task, NAP, Schedule

gantt = Schedule()

tasks and NAP for machine 0

gantt.add_task(Task(0,0,0,35)) gantt.add_NAP(NAP(0,35,60,'BKDOWN')) gantt.add_task(Task(1,0,60,68))

tasks and NAP for machine 1

gantt.add_task(Task(1,1,0,10)) gantt.add_NAP(NAP(1,10,30,'SETUP')) gantt.add_task(Task(0,1,35,70))

printing the schedule

gantt.print()


creates tasks and NAP and add them to the schedule in the figure 

[[/images/Several_NAP_sample.png]]

## Advanced usage of Gantt charts: An example

Clearly, the idea of the Tasks and NAPs is not to be used in an isolated manner, but to integrate them into a (possibly customised) scheduling model. As it has been discussed in Section , to obtain a customised scheduling model, it is only required to create a child class of the class `Model` and to write the specific code for the constructor method (where the data required are defined) and for the `ct` method (where the completion times for each job in a given job order are computed). In addition, to include a customised Gantt chart, we would also need to overwrite the parent method `print_schedule`, as this method in the class `Model` does not consider NAPs. To illustrate the whole process, in this section we will present a single machine scheduling model with sequence-dependent setup and release times. This new model (named `SingleMachineSetUp`) not only will compute the usual scheduling criteria, but also will print a schedule that takes into account the sequence-dependent setups. The full code for this model is the following:

from scheptk.scheptk import Model, NAP from scheptk.util import *

class SingleMachineSetUp(Model):

# constructor
def __init__(self, filename):
    self.jobs = read_tag(filename,'JOBS')
    self.pt = read_tag(filename,'PT')
    self.sj = read_tag(filename,'SJ')
    self.r = read_tag(filename,'R')

# compute completion times (assumed anticipatory setup)
def ct(self, solution):
    ct = [0 for j in range(len(solution))]
    ct[0] = max(self.r[solution[0]],self.sj[solution[0]][solution[0]]) + self.pt[solution[0]] 
    for j in range(1,len(solution)):
        ct[j] = max(self.r[solution[j]],ct[j-1] + self.sj[solution[j]][solution[j-1]]) + self.pt[solution[j]] 
    return [ct], solution

# print customised schedule
def print_schedule(self, solution, filename=None):
    completion_time, sol = self.ct(solution)
    gantt = Model.create_schedule(self,solution)
    gantt.add_NAP(NAP(0,0, self.sj[solution[0]][solution[0]],'SETUP'))
    for j in range(1,len(solution)):
        st = completion_time[0][j] - self.pt[solution[j]] - self.sj[solution[j]][solution[j-1]]
        gantt.add_NAP(NAP(0,st, st + self.sj[solution[j]][solution[j-1]],'SETUP'))
    gantt.print(filename)



As we can see, a `SingleMachineSetUp` class has been defined as a child of the parent class `Model`. This allows `SingleMachineSetUp` to use all methods for scheduling layouts once we provide an specific way to enter the data and to compute the completion times from this data. The data of the model are described in the constructor `__init__(self, filename)`, where the data are `jobs` (an integer indicating the number of jobs), `pt` (an array indicating the processing time of each job), `r` (an array with the release date of each job), and `sj`, which requires a more detailed explanation. Although there are different possibilites --after all, it is a customised model so we define which data are required and how are used--, we  define `sj` as a two-dimensional array. In this manner `sj[k][l]` indicates the setup time required when job `l` is processed immediately after job `k`. To model the need to introduce a setup time if no prior job has been entered in the sequence, `sj[k][k]` would contain this initial setup time. 

With the constructor method, an instance data file would look like this

[JOBS=3] [PT=20,35,38] [R=10,10,10] [SJ=0,12,25;5,40,2;30,12,0]


So in this instance there are three jobs (with processing times 20, 35 and 38 respectively, and release times 10, 10 and 10), and the setup times are as follows:


| Job/job  | 0     | 1     | 2     |
| ----------- | ---- |----    |----  |
| 0    | 0     | 12     | 25     |
| 1    | 5     | 40     | 2     |
| 2    | 30     | 12     | 0     |

which means that, if job 1 is processed immediately after job 0, then a setup time of 5 units is required.

The second method (`ct`) computes the completion times. Remember that the method takes as input a solution of the problem, and returns the completion times on each machine, and the order in which the completion times of the jobs are given. In our case, a solution would be a (maybe partial) list of jobs, so `sol = [2,0,1]` would indicate that job 2 is processed first, next job 0, and finally job 1.

The first line in the `ct` method simply creates a list with the completion times of the jobs entered in the solution, and initially these completion times are zero. Next, for the first job, it simply computes the completion time as `ct[0] = max(self.r[solution[0]],self.sj[solution[0]][solution[0]]) + self.pt[solution[0]]`, i.e. the completion time of the first job is the maximum between the release date of the job and its initial setup time plus the processing time of the job. Next is a loop where the completion time of the other jobs are computed. In this case, the completion time is the maximum between the release date of the job and the completion time of the previous job in the machine plus the setup time required plus the processing time of the job. The method returns the completion time of each job in the solution __and__ the order in which the jobs are described in the completion times.

In principle, with this two methods would be sufficient to compute the usual criteria. If the following code is produced (using the instance data file `single_setup.txt` provided above)

from scheptk.scheptk import Model, NAP instance = SingleMachineSetUp('single_setup.txt') solution = [2,0] print('Makespan=',instance.Cmax(solution)) print(solution)


[[/images/SingleMachineSetUp_No_NAP_sample.png]]

then the makespan is correctly computed, but when the schedule is printed, there is a void of 25 periods between the processing time of job 0 and that of job 2. This void corresponds to the setup induced when job 0 is processed after job 2 (see setup matrix). If the setups are entered in the `Schedule`as non-availability periods, then they could appear in the schedule. This is the goal of the third method (`print_schedule`). The first line of this method is to call the `ct` nethod to obtain the completion times (as later these completion times would be used). The second line simply calls the method `create_schedule` of the parent class `Model`. This line will create a standard schedule using the solution, that is, it will create all tasks corresponding to the solution without the NAPs. Then the NAPs are added to the schedule: the first line (`gantt.add_NAP(NAP(0,0, self.sj[solution[0]][solution[0]],'SETUP'))`) adds a NAP starting at time zero and finishing at the time required for the initial setup. The label of the NAP is `SETUP`. The rest of the non availability periods are added using a loop: the starting time is computed (completion time minus setup minus processing time), and then are added. The last line simply prints the schedule, now with all setup times properly set, as it can be seen in the figure.

[[/images/SingleMachineSetUp_NAP_sample.png]]

By the way, the figure shows another feature related to printing the Gantt charts: if the NAPs are of zero length (as it happens with the job 2), then the NAP is not printed. 
Welcome to the `scheptk` Wiki. These pages are primarily intended as a documentation for users and developers of scheptk.

Although, in general, the wiki is not intended to be read in a sequential manner, a possible reading order for users approching `scheptk` for the first time is the following:

1. [[Start using scheptk]]. In this section you may read [how to install](Start-using-scheptk#installation) `scheptk`, [how to write the first program](Start-using-scheptk#overview) using `scheptk` and [how solutions of a scheduling model are represented](Start-using-scheptk#obtaining-schedules).
1. [[List of scheduling environments]]. In this section, the following scheduling models implementd in `scheptk` are described in detail.  These models are
    - [Single Machine](List-of-scheduling-environments#single-machine) 
    - [Parallel Machines](List-of-scheduling-environments#parallel-machines)
    - [Unrelated Machines](List-of-scheduling-environments#unrelated-machines)
    - [Flow Shop](List-of-scheduling-environments#flow-shop)
    - [Job Shop](List-of-scheduling-environments#job-shop)
    - [Open Shop](List-of-scheduling-environments#open-shop)


    For each model the following information is provided:
    - A physical description
    - The attributes of the class, i.e. the input data required to create and maintain an instance of the model.
    - A sample instance file.
    - The way a solution for this scheduling problem is encoded.
    - A sample code.

1. [[Measuring a solution]]. In this section you may learn about the methods implemented in `scheptk` to compute [job-machine-level](Measuring-a-solution#job-machine-level-measures) (i.e. completion times) and [job-level measures](Measuring-a-solution#job-level-measures) (such as e.g. completion times of the jobs, their lateness, etc), once a solution is provided for a scheduling model.


1. [[List of scheduling criteria]]. In this section, the scheduling criteria handled by `scheptk` are listed.

1. [[Some useful functions]]. In addition to scheduling models, `scheptk` includes a number of functions to facilitate the development of programs. These are grouped in the `scheptk.util` package and include [functions to sort lists](Some-useful-functions#sorting-functions), [functions to produce random solutions](Some-useful-functions#obtaining-random-solutions), and [functions to write, read and edit file tags](Some-useful-functions#tags).

1. [[Creating customised models]]. This section (and the folllowing one) is intended for advanced users who might want to create their own models. This requires a bit of knowledge on [how the parent class](Creating-customised-models#the-model-class) `Model` works, and how new models can be derived from this class by stating the [input data](Creating-customised-models#implementing-a-constructor-for-the-customised-model) required in the constructor of the class, and implementing [how to compute `ct` for this customised model](Creating-customised-models#implementing-a-method-to-compute-the-completion-times).

1. [[Handling schedules and Gantt charts]]. It is possible that customised models require specific representations to graphically depict the Gantt chart. This section is devoted to explain how customised Gantt charts can be created using `scheptk`. 





 Classic scheduling criteria seek to minimize the maximum value or the sum of values across jobs of a [job-level measure](/Measuring-a-solution.md). The first are denoted as [min-max type](#min-max-type) criteria whereas the second are denoted as [min-sum type](#min-sum-type) criteria. Both are presented in the next sections.


# Min-max type



 * `Cmax(solution)` - computes the makespan or maximum completion time of the solution given in `solution`.
 * `Emax(solution)` - computes the maximum earliness of the solution given in `solution`.
 * `Fmax(solution)` - computes the maximum flowtime of the solution given in `solution`.
 * `Lmax(solution)` - computes the maximum lateness of the solution given in `solution`.
 * `Tmax(solution)` - computes the maximum tardiness of the solution given in `solution`.
 * `max_WjCj(solution)` - computes the weighted makespan or maximum completion time of the given in `solution`.
 * `max_WjEj(solution)` - computes the weighted maximum earliness of the solution given in `solution`.
 * `max_WjFj(solution)` - computes the weighted maximum flowtime of the solution given in `solution`.
 * `max_WjLj(solution)` - computes the weighted maximum lateness of the solution given in `solution`.
 * `max_WjTj(solution)` - computes the weighted maximum tardiness of the solution given in `solution`.
 

# Min-sum type

 * `SumCj(solution)` - computes the sum of the completion times of the solution given in `solution`.
 * `SumEj(solution)` - computes the sum of the earliness of the solution given in `solution`.
 * `SumFj(solution)` - computes the sum of the flowtime of the solution given in `solution`.
 * `SumLj(solution)` - computes the sum of the lateness of the solution given in `solution`.
 * `SumTj(solution)` - computes the sum of the tardiness of the solution given in `solution`.
 * `SumUj(solution)` - computes the sum of the tardy jobs in the solution given in `solution`.
 * `SumWjCj(solution)` - computes the sum of the weighted completion times of the solution given in `solution`.
 * `SumWjEj(solution)` - computes the sum of the weighted earliness of the solution given in `solution`.
 * `SumWjFj(solution)` - computes the sum of the weighted flowtime of the solution given in `solution`.
 * `SumWjLj(solution)` - computes the sum of the weighted lateness of the solution given in `solution`.
 * `SumWjTj(solution)` - computes the sum of the weighted tardiness of the solution given in `solution`.
 * `SumWjUj(solution)` - computes the sum of the weighted tardy jobs in the solution given in `solution`.






# 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|Creating-customised-models]]. The standard scheduling models implemented in `scheptk` are the following:
- [Single Machine](#single-machine) (`SingleMachine` class)
- [Parallel Machines](#parallel-machines) (`ParalleMachines` class)
- [Unrelated Machines](#unrelated-machines) (`UnrelatedMachines` class)
- [Flow Shop](#flow-shop) (`FlowShop` class)
- [Job Shop](#job-shop) (`JobShop` class)
- [Open Shop](#open-shop) (`OpenShop` class)



# Single Machine

The `SingleMachine` 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.

[[/images/single_sample.png]]

## Attributes

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

The `ParallelMachines` 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.

[[/images/parallel_sample.png]]


## Attributes

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
> * `machines` - number of machines
> * `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

The `UnrelatedMachines` 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.

[[/images/unrelated_sample.png]]

## Attributes

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
> * `machines` - number of machines
> * `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 instance = UnrelatedMachines('test_unrelated.txt') sequence = [5, 1, 4, 2, 3, 0] instance.print_schedule(sequence) print(instance.Cj(sequence))



# Flow Shop

The `FlowShop` 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.


[[/images/flowshop_sample.png]]

## Attributes

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
> * `machines` - number of machines
> * `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

The `JobShop` 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.


[[/images/jobshop_sample.png]]

## Attributes

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
> * `machines` - number of machines
> * `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 possibilities 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

The `OpenShop` 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.

[[/images/openshop_sample.png]]

## Attributes

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
> * `machines` - number of machines
> * `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')


Once a solution for one of scheduling models presented [here](List-of-scheduling-criteria) has been devised, different measures of the merits of the solution can be obtained. These are of two types:

- [Measures at job-machine level](#job-machine-level-measures)
- [Measures at job level](#job-level-measures)

# Job-machine level measures

There are two basic job-machine level indicators of a solution. The first one is `ct`, which provides a list of the completion time of each job on each machine. Therefore `ct[i][j]` indicates the completion time on machine `i` of the job provided in the solution in order `j`. For most of the basic scheduling models included in the library, the solution is given in the form of a sequence of jobs, but it is not always the case (for instance, for the `JobShop` and `OpenShop` models, that use different solution encodings). Therefore, along with the completion times of the jobs on the machines, the order in which the jobs are presented in the list of completion times should be given. This is particularly important in the case of _partial_ solutions (i.e. solutions that only contain some of the jobs to be scheduled). Let us consider the following example for the `SingleMachine` environment:

from scheptk.scheptk import SingleMachine

instance = SingleMachine('test_single.txt') sequence = [2,1] completion_times, job_order = instance.ct(sequence)

print(completion_times) print(job_order)


Note that the solution provided in `sequence` is a partial sequence, as it contains jobs 1 and 2, but no job 0 (and possible other jobs). If the file `test_single.txt` contains the following tags: `[JOBS=4]` and `[PT=2,10,1,1]`, then the result of the above code is the following:

1, 11 [2, 1]


The first line (the printing of `completion_times`) contains a list with one row with two columns. Therefore `ct[0][0]` contains the completion time on the first (and only) machine of the first job in the solution (job 2), whose processing time is 1. The `ct[0][1]` contains the completion time on the first machine of the second job in the solution (job 1), whose processing time is 10 (which results in a completion time of 1 + 10 = 11). The second line (the printing of `job_order`) contains an order that indicates what job corresponds to each row in `ct`. In the example, it indicates that the first column in the list in `ct` corresponds to the completion times of job 2, whereas the second column contain the completion times of job 1.

While for some models (i.e. `SingleMachine`, `ParallelMachines`,`UnrelatedMachines` and `FlowShop`), `job_order` is the same as the solution provided, this is not true for `JobShop` and `OpenShop` models, which have extended solution encoding. Note the following code:

from scheptk.scheptk import OpenShop

instance = OpenShop('test_openshop.txt') sol = [7,5,4,0,1,6,3,2,8] print(sol) ct, order = instance.ct(sol)

print(ct) print(order) instance.print_schedule(sol)


When the data in `test_openshop.txt` are given by the following tags:

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


then the output is

[7, 5, 4, 0, 1, 6, 3, 2, 8] 41, 59, 10], [36, 6, 51], [16, 67, 26 [1, 2, 0]


and the figure 


[[/images/openshop_sample.png]]

In this case `ct[0][0]` contains the completion time on machine 0 of the first job in the order given by `order` (i.e. job 1), and e.g. `ct[1][2]` contains the completion time on machine 1 of the third job in the order given by `order` (i.e. job 0). As we can see, in this case the information given in `order` is useful, as the solution `sol` does contain operations and not jobs, and therefore the job order is not clear in the solution.

Whenever one job is not processed in some specific machine (as, for instance, it happens in the `ParallelMachines` and `UnrelatedMachines`) models, the corresponding processing times in `ct` are zero.

Using `ct` and particularly returning the job order may seen a bit complex but it allows us to handle partial solutions (as we have seen in the `SingleMachine` example) in a compact manner, as otherwise the completion times of the jobs in `ct` would be hard to express, since job 0 is not in the partial solution and therefore `ct[0][0]` cannot indicate the completion time on machine 0 of job 0.


An alternative to `ct` is the method `ctn`, which provides the completion time of __all__ the jobs in the machines. Here `ct[i][j]` indicates the completion time on machine `i` of the job `j`. If job `j` has not been scheduled (because i.e. the solution is a partial solution), then a `nan` (not available number) is returned in its place. Therefore, the following code:

from scheptk.scheptk import SingleMachine

instance = SingleMachine('test_single.txt') sequence = [2,1] completion_times, job_order = instance.ct(sequence)

print(completion_times) print(instance.ctn(sequence))


when the `test_single.txt` instance contains the same data as above produces the following output:

1, 11 nan, 11, 1, nan


Note the difference between the completion times provided by `ct` and those provided by `ctn`: `ctn[0][0]` indicates the completion time on machine 0 of job 0. Since job 0 is not part of the solution provided, its completion time is `nan`. `ct[0][1]` contains the completion time of job 1 on machine 0. This job is the second job in the partial solution provided, hence its completion time is higher than that of job 2 (which is the first job provided in the partial solutions).

A final, additional example is provided next for the `UnrelatedlMachines` model. The following code

from scheptk.scheptk import UnrelatedMachines

instance = UnrelatedMachines('test_unrelated.txt') sequence = [2,5,0,4] ct, order = instance.ct(sequence) print(ct) print(instance.ctn(sequence)) instance.print_schedule(sequence, 'unrelated_partial_sample.png')


with the data given in the tags `[JOBS=6]`, `[MACHINES=2]`, `[PT=5,13,5,2,8,6;9,12,10,4,3,10]` yields the following results

5, 0, 10, 0], [0, 10, 0, 13 10, nan, 5, nan, 0, 0], [0, nan, 0, nan, 13, 10


and the following figure

[[/images/unrelated_partial_sample.png]]



## A final remark on `ct` and `ctn`

As we have seen, information regarding the completion times is provided by the functions in `scheptk` using two alternatives, `ct` and `ctn`. Both approaches have pros and cons, and whereas it is clear that `ct` provides a more compact way to handle partial solutions and the information is clearer in scheduling models whose solution encoding consists of a sequence, the interpretation is more confusing than `ctn` for `JobShop`, `OpenShop` models, or models with sophisticated solution encodings. `scheptk` provides both, so it is up to the user to pick the one that fits better for him/her.

# Job-level measures

Job-level measures usually aggregate (or combine with additional data) job-machine level measures. Job-level measures can be computed using a number of methods described below, and  indeed these methods are internally called by the models to obtain [scheduling criteria](/List-of-scheduling-criteria.md).

The most classical job-level measure are the completion times of the jobs in a solution. These can be obtained with the method `Cj(solution)` that returns a list of the completion times of each job in the solution _in the order of the jobs provided in the solution_. More specifically, the following code

from scheptk.scheptk import SingleMachine instance = SingleMachine('test_single.txt') completion_times = instance.Cj( [2,0] ) print(completion_times)


for the instance with tags `[JOBS=4]` and `[PT=2,10,1,1]` yields the following output:

[1, 3]

which corresponds to first processing job 2 (with processing time 1) and then job 0 (with processing time 2). Therefore `completion_time[0]` contains the completion time of the first processed job (job 2) while `completion_time[1]` contains the completion time of the second processed job (job 0).


In the same manner than `ct` and `ctn` in the section above, an alternative to obtain the completion times of the jobs is to use the method `Cjn(solution)` --note the difference of the `n`--, which provides the completion time of __all__ jobs (even if they are not part of the solution) in the natural job order. More specifically, just changing the third line in the code above by `completion_times = instance.Cjn( [2,0] )`, the following output is produced:

[3, nan, 1, nan]


which indicates that job 0 has a completion time of 3, that job 1 is not part of the solution and hence its completion times are not available (`nan`), that job 2 has a completion time of 1, and that job 3 is not part of the solution.

Similarly to the completion times, the following additional methods are available to compute job-level measures:


* `Ej(solution)` - returns a list with the earliness of each job in `solution`. The order of the values is that of the jobs in `solution` (as in `Cj`).
* `Ejn(solution)` - returns a list with the earliness of __all__ jobs according to  `solution`. The order of the values is the natural order (as in `Cjn`).
* `Fj(solution)` - returns a list with the flowtime of each job in `solution`. The order of the values is that of the jobs in `solution` (as in `Cj`).
* `Fjn(solution)` - returns a list with the flowtime of __all__ jobs according to  `solution`. The order of the values is the natural order (as in `Cjn`).
* `Lj(solution)` - returns a list with the lateness of each job in  `solution`. The order of the values is that of the jobs in `solution` (as in `Cj`).
* `Ljn(solution)` - returns a list with the lateness of __all__ jobs according to  `solution`. The order of the values is the natural order (as in `Cjn`).
* `Sj(solution)` - returns a list with the starting time in the system of each job in `solution`. The order of the values is that of the jobs in `solution` (as in `Cj`).
* `Sjn(solution)` - returns a list with the starting time in the system of __all__ jobs according to `solution`. The order of the values is the natural order (as in `Cjn`).
* `Tj(solution)` - returns a list of with tardiness of each job in `solution`. The order of the values is that of the jobs in `solution` (as in `Cj`).
* `Tjn(solution)` - returns a list of with tardiness of __all__ jobs according to  `solution`. The order of the values is the natural order (as in `Cjn`).
* `Uj(solution)` - returns a list indicating if a job in `solution` is tardy (1), or not (0). The order of the values is that of the jobs in `solution` (as in `Cj`).
* `Ujn(solution)` - returns a list indicating if each job is tardy (1), or not (0), according to `solution`.  The order of the values is that of the jobs in `solution` (as in `Cj`).

# Introduction

`scheptk.util` contains a number of functions that are useful to develop scheduling models. While some of these functions are intended to be used internally by `scheptk`, some of them can be useful to build algorithms. The functions can be grouped in:

- [Sorting functions](#sorting-functions), so lists are sorted according to values and the corresponding indices of the lists are obtained.
- [Random sequences](#obtaining-a-random-sequence), i.e. how to generate a list containing a random sequence of a given length.
- [Tag-related functions](#tags), including how to [write](#writing-tags) tags in a (existing or new) file, read [tags](#reading-a-tag-from-a-file) from a file, and [edit](#editing-tags) tags in an existing file.



# Sorting functions

* `sorted_index_asc(list)` returns a list containing the ordered (ascending order) indices of the elements in `list`. The following code:

from scheptk.util import sorted_index_asc

processing_times = [10,69,5,28,12] jobs_SPT_order = sorted_index_asc(processing_times) print(jobs_SPT_order)


produces the output `[2, 0, 4, 3, 1]`

* `sorted_index_desc(list)` returns a list containing the ordered (descending order) indices of the elements in `list`. The following code:

from scheptk.util import sorted_index_desc

processing_times = [10,69,5,28,12] jobs_LPT_order = sorted_index_desc(processing_times) print(jobs_LPT_order)


produces the output `[1, 3, 4, 0, 2]`


* `sorted_value_asc(list)` returns a list containing the ordered (ascending order) elements in `list`. The following code:

from scheptk.util import sorted_value_asc

processing_times = [10,69,5,28,12] ordered_processing_times = sorted_value_asc(processing_times) print(ordered_processing_times)


produces the output `[5, 10, 12, 28, 69]`


* `sorted_value_desc(list)` returns a list containing the ordered (descending order) elements in `list`. The following code:

from scheptk.util import sorted_value_desc

processing_times = [10,69,5,28,12] ordered_processing_times = sorted_value_desc(processing_times) print(ordered_processing_times)


produces the output `[69, 28, 12, 10, 5]`


# Obtaining random solutions

## Random sequences

Many solutions of scheduling problems take the form of a sequence of jobs, i.e. `solution=[2,1,4,3]`. The function `random_sequence(size)` produces a random sequence of lenth `size`, i.e. the following code

from scheptk.util import random_sequence random_seq = random_sequence(8) print(random_seq)


produces the following output (note the sequence is random, so it might be different every time)

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


For those interested in random numbers generation, note that `random_sequence()` does not initialise the seed in the pseudorandom stream.



## Random extended sequences (`JobShop`)

The solution encoding implemented for the `JobShop` model is that of [extended sequences](List-of-scheduling-environments#solution-encoding-4), therefore obtaining a random feasible solution requires that there are exactly `m` occurrences of each one of the `n` jobs. Such solution can be obtained using the `random_extended_sequence(jobs, machines)` function, which produces a random feasible solution for a `JobShop` with `machines` machines and `jobs` jobs, i.e. the following code:

from scheptk.scheptk import JobShop from scheptk.util import random_extended_sequence

instance = JobShop('test_jobshop.txt') random_sol = random_extended_sequence(instance.jobs, instance.machines) print(random_sol) instance.print_schedule(random_sol)


produces a feasible random solution for the instance of the `JobShop` model. As with `random_sequence`, the way the pseudo-random numbers are generated relies on the standard `random` Python library, so users that might want to ensure _true pseudorandomness_ or to control the pseudorandom stream can built their own functions.

# Tags

Tags are the main way for `scheptk` to handle scheduling data. Most of the times, this is done by the scheduling models, but in the case that one might want to develop [[customised scheduling models|Creating-customised-models]], then some of the following functions are needed:

* `write_tag(tag_name, tag_value, filename)` to write a tag
* `read_tag(filename, tag_name)` to read a tag
* `edit_tag(tag_name, tag_value, filename)` to edit an existing tag




These functions are discussed in the next subsections.

## Writing tags

The function `write_tag(tag_name, tag_value, filename)` writes an additional line in `filename` containing the `tag_name` tag with the value in `tag_value`. Note that `tag_value` may be an scalar, a list, or a list of lists. The following code

from scheptk.util import write_tag

write_tag('JOBS',3,'data.txt') write_tag('PROCESSING_TIMES',[10,45,30],'data.txt') write_tag('SETUP_TIMES',10,4,3],[2,6,7],[9,12,1,'data.txt')


produces the following output

[JOBS=3] [PROCESSING_TIMES=10,45,30] [SETUP_TIMES=10,4,3;2,6,7;9,12,1]


## Reading a tag from a file

The function `read_tag(filename, tag_name)` opens the file `filename` and searchs for a tag named `tag_name` (an error is launched if the filename is not found). If the tag is found, it returns the value of the tag (whether it is a scalar, list, or list of lists). If the tag is not found, it returns -1. The following code

from scheptk.util import read_tag

setups = read_tag('data.txt','SETUP_TIMES') print(setups)


returns (assumed that `data.txt` contains the output as in the file described in [Writing tags](#writing-tags))

10, 4, 3], [2, 6, 7], [9, 12, 1


## Editing tags

The function `edit_tag(tag_name, tag_value, filename)` opens the file `filename` and searchs for a tag named `tag_name` (an error is launched if the filename is not found). If the tag is found, it edits the content of the tag (substituting it with `tag_value`) and returns the line of the file where the tag was found. If the tag is not found, it returns -1. ## Installation

`scheptk` can be installed using PIP. Copy and paste the command to install it from [here](https://pypi.org/project/scheptk/), or type in the console

pip install scheptk


If you have `scheptk` already installed, make sure to have the latest [version](https://pypi.org/project/scheptk/) by typing

pip install --upgrade scheptk


The installed version of `scheptk` can be checked by typing

pip show scheptk



## Overview

scheptk contains two main modules:

* `scheptk` where the main scheduling classes and their methods are included.
* `util` contains a number of functions, some employed by the classes internally.

A typical program runs like this:

from scheptk.scheptk import * from scheptk.util import *

instance = SingleMachine('test_single.txt') sequence = sorted_index_asc(instance.dd) print('EDD sequence for the instance is: ', end='') print(sequence) completion_time = instance.SumCj(sequence) print('The total completion time of the sequence is {}'.format(completion_time))



The program starts by instantiating one of the scheduling layout classes (i.e. `SingleMachine`, `ParallelMachines`,`UnrelatedMachines`, `FlowShop`, `JobShop` or `OpenShop`).Each one of these classes contains all the data that describe a scheduling instance of the corresponding type (such as jobs, processing times, due dates, etc). These data are typically loaded from a text file where they are contained in tags. Here is the content of such text file for a `SingleMachine` instance:

[JOBS=3] [PT=10,15,6] [DD=50,65,60]


In this example, it is defined an instance of a single machine scheduling problem with 3 jobs, each one with the processing times 10,15 and 6, and the due dates 50,65 and 60.

Some of these data (such as the number of jobs and the processing times) are mandatory while others (such as the due dates) are optional. The full list of data for each type of instance is provided [[here|List-of-scheduling-environments]].

Once the data have been loaded into an object, they are accessible as attributes of the class:

print('The number of jobs is {}'.format(instance.jobs))



The full list of attributes for each type of layout can be found [[here|List-of-scheduling-environments]].

A solution for the instance can be entered or computed using some algorithm. This solution can be evaluated regarding the most common scheduling criteria. The list of scheduling criteria supported can be found [[here|List-of-scheduling-criteria]]

from scheptk.scheptk import *

instance = SingleMachine('test_single.txt') solution = [1,0,2] print('The maximum tardiness of the solution is {}'.format(instance.Tmax(solution)))



The first line of the previous example loads the instance of the single machine scheduling problem. The second defines a solution for the problem, in this case a sequence that specifies that job 1 is scheduled first, then job 0 and finally job 2. The third line simply print the maximum tardiness (Tmax) corresponding to the solution.

# Obtaining schedules

The corresponding no-idle schedule of the solution of an instance can be obtained using `print_schedule(solution)`. Optionally, this schedule can be printed into a `.png` or `.jpg` file as `print_schedule(solution, file)`. The following code:

from scheptk.scheptk import OpenShop

instance = OpenShop('test_openshop.txt') sol = [7,5,4,0,1,6,3,2,8] instance.print_schedule(sol)


produces the following schedule:

[[/images/openshop_sample.png]]



The manipulation of the schedules and Gantt charts is discussed [[here|Handling-schedules-and-Gantt-charts]].


## Table of contents
- [[Home]]
- [[Start using scheptk]]
- [[List of scheduling environments]]
- [[Measuring a solution]]
- [[List of scheduling criteria]]
- [[Handling schedules and Gantt charts]]
- [[Some useful functions]]
- [[Creating customised models]]

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

allfiles

Overview

The `Model` class

Implementing a constructor for the customised model

Implementing a method to compute the completion times

tasks and NAP for machine 0

tasks and NAP for machine 1

printing the schedule

Table of contents

Clone this wiki locally

allfiles

Overview

The Model class

Implementing a constructor for the customised model

Implementing a method to compute the completion times

tasks and NAP for machine 0

tasks and NAP for machine 1

printing the schedule

Table of contents

Clone this wiki locally

The `Model` class