Creating customised models

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. The Model class contains five methods that should be instantiated by each children class, i.e.

• __init__(), the constructor where the data of the model are defined
• random_solution() a method that returns a random solution (in a user-defined solution encoding)
• ct(solution) a method that takes a solution (in a user-defined solution encoding) and returns the completion time of each job on each machine
• Cj(solution) a method that takes a solution (in a user-defined solution encoding) and returns the completion time of each job. Usually it calls the method ct() internally.
• create_schedule(solution) a method that returns an instance of the Schedule class containing the schedule corresponding to the solution specified.

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. For brevity, create_schedule() and random_solution() are not implemented, so schedules cannot be visualised or random solutions are obtained. These are detailed later on.

from scheptk.scheptk import Model
from scheptk.scheptk 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_1 = read_tag(filename,'PT_MACHINE_1')
        self.pt_2 = read_tag(filename,'PT_MACHINE_2')
        self.pt_a = read_tag(filename,'PT_ASSEMBLY')

    # computes the completion time of each job on each machine
    # usually it will be used internally for Cj() and for create_schedule()
    def ct(self, solution):

        # completion time of the jobs on each machine
        ct_machine_1 = [0 for j in range(self.jobs)]
        ct_machine_2 = [0 for j in range(self.jobs)]
        ct_assembly = [0 for j in range(self.jobs)]

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

        for job in solution:

            # compute completion times of each job in the first stage
            ct_machine_1[job] = earliest_st_machine_1 + self. pt_1[job] 
            ct_machine_2[job] = earliest_st_machine_2 + self. pt_2[job] 
            
            # compute completion time of each job in the assembly stage
            ct_assembly[job] = max(earliest_st_assembly, max(ct_machine_1[job], ct_machine_2[job])) + self.pt_a[job]
            
            # update earliest completion times of the machines in the stages
            earliest_st_machine_1 = ct_machine_1[job] 
            earliest_st_machine_2 = ct_machine_2[job] 
            earliest_st_assembly = ct_assembly[job]
        
        return ct_machine_1, ct_machine_2, ct_assembly
        
    
    # compute the completion time of the jobs
    # usually they are computed by calling ct()
    def Cj(self, solution):

        ct_machine_1, ct_machine_2, ct_assembly = self.ct(solution)

        return ct_assembly


    def random_solution(self):
        print('Not yet implemented')


    # creates an schedule
    # usually it requires ct()
    def create_schedule(self, solution):
        print('Not yet implemented')

Once this code has been entered, all functions of a scheduling model (with the exception of visualising schedules and random solutions) are available, i.e.:

instance = Assembly_2_machines('assembly_sample.txt')

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

Introduction to creating scheduling models

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.

Data

In general, there are two types of data in a scheduling problem: input data (the data required to make the scheduling decision) and output data (the data that constitute the decision). For instance, the jobs, machines and processing times are input data of a scheduling model, and an schedule indicating when each job is processed on each machine are output data. For the sake of brevity, the set of input data will be denoted as a model, and output data will be denoted as schedule.

Both types can be persistent (i.e. we might want to save them in a file and store them after the program is run), or temporary (i.e. we might want to load them in the memory of the program to use them). In scheptk, persistent data are stored in files and specified by tags

The Model class

The model class is the parent class of all scheduling models in scheptk. It contains some attributes that are common to all scheduling models.