Some useful functions

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, so lists are sorted according to values and the corresponding indices of the lists are obtained.
• Random sequences, i.e. how to generate a list containing a random sequence of a given length.
• Tag-related functions, including how to write tags in a (existing or new) file, read tags from a file, and edit 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, 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, 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)

[[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.