Single Machine Scheduling
Contents:
Opt.c: The C code of the algorithm BETA
which is developed by :
Barbaros C. Tansel
Bahar Yetis Kara
Ihsan Sabuncuoglu
There are 3 different executible files of Opt.c . They differ in the construction of the Beta-Sequence. We use LEFT-EXPAND for sure, but how to use RIGHT-EXPAND makes the differences:
- The Beta-Sequence can be constructed via LEFT-EXPAND only,
- One step RIGHT-EXPAND can be used right after LEFT-EXPAND, during the construction of the Beta-Sequence,
- The Beta-Sequence can be constructed by alternating usage of LEFT-EXPAND and RIGHT-EXPAND until:
- - the Beta-Sequence is either optimum or it decomposes at some job q, OR
- - no more updating occurs on the Beta-j values.
left: Executible file of Opt.c which uses LEFT-EXPAND only during the construction of the Beta-Sequence.
leftright: Executible file of Opt.c which uses one step RIGHT-EXPAND after LEFT-EXPAND.
full: Executible file of Opt.c which uses LEFT-EXPAND and RIGHT-EXPAND alternatingly.
Since these executible files differ in the construction of the Beta-Sequence, they may result in different processing times and b&b tree for the same instance.
We suggest that you use left if number of jobs in consideration is <= 300 and use leftright if number of jobs is between 400 and 500, to achieve the least CPU time usage.
There are some problem types for which the solution time exceeds the time limit (80hr). The detailed explanation of those problem types are given in ExplainTestFiles.
InputStructure:
The input file should contain 4 types of information in four main lines.
The first line should contain the number of jobs,
the second line should contain the (R, T) information given in that order,
the third line should contain the process times in integer values, and finally
the last line should contain the due dates (again integer).
The files exdata1 and exdata2 are example input files.
OutputStructure:
The output file contains all the information of its input file followed by the optimum sequence. The optimum sequence is given by its indeces and the indeces start from 0.
HowToRun:
In order to run an executible file of Opt.c, you need to define a file which
contains the name of inputfile(s) that you want to solve and corresponding
output files. You can run the programs with 1 data set or more.
For example, exin1 is such a file. It will take the input file exdata1, and
after solving that problem will write the result in exoutput1.
In exin2, two consequtive examples are solved. The program will first solve
exdata1, and then solve exdata2.
While running the program you write in the command prompt :
left exin1
which will use the executible file left in solving the exdata1.