Open AccessInstances generation for a single machine scheduling problem
Author(s) -
Alexander A. Lazarev,
Nikolay Pravdivets,
Egor Grishin,
S. A. Galakhov
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1864/1/012057
Subject(s) - branch and bound , computer science , scheduling (production processes) , mathematical optimization , minification , search tree , upper and lower bounds , single machine scheduling , algorithm , mathematics , job shop scheduling , search algorithm , schedule , mathematical analysis , operating system
The branch and bound method is used to obtain exact solutions of the single machine scheduling problem with the objective function of maximum lateness minimization. Lower bounds are estimated by solving dual problems. A machine-independent value, namely the number of branching points in the search tree, is used as the complexity index of instances. The instances are presented as points in 3n-dimensional space. Known and newly developed ways of instances generation (with a large number of branching points) are presented, and the advantages and disadvantages of each of them are described.