This paper deals with an adaptive approach for scheduling problems. The main idea is to produce, for a class of similar problems, a special heuristic rule which is successful for problems of this class. It is realised by ‘tuning’ the parameters of the algorithm while ‘learning’ on the peculiarities of considering a class of problems. Once trained on the sample problems (in our experiments a well-known test problem with 10 jobs and 10 machines has been considered), the adaptive algorithm solves ‘close’ problems better than a branch and bound algorithm with a time limit (both in running time and in accuracy of the constructed schedule) and better than the 25 heuristics (in accuracy) used in the learning stage. However, the adaptive algorithm is unable to perform better than the branch and bound algorithm with a time limit for such scheduling problems, which are not sufficiently close to the sample problem.
References
-
-
1)
-
Sotskov, Yu.N.: ‘Constructing an optimal makespanschedule forprocessing jobsby sequential machines’, Institute of Engineering Cybernetics of Academy of Sciencesof Belarus, 1981, pp. 28–34 (in Russian).
-
2)
-
V.S. Tanaev ,
Yu.N. Sotskov ,
V.A. Strusevich
.
(1994)
Scheduling theory. Multistage systems.
-
3)
-
M.R. Garey ,
D.S. Johnson
.
(1979)
Computers and intractibility: a guide to the theory of NP-completeness.
-
4)
-
E. Balas
.
Machine sequencing via disjunctive graphs: an implicit enumeration algorithm.
Oper. Res.
,
941 -
957
-
5)
-
J.F. Muth ,
G.L. Thompson
.
(1963)
Industrial scheduling.
-
6)
-
R. Haupt
.
A survey of priority rule-based scheduling.
OR Spektrum
,
278 -
285
-
7)
-
Sotskov, Yu.N., Shakhlevich, N.V.: `An adaptive approach in production scheduling based on the mixed graphmodel', 395, Second international conference on Intelligent systems engineering, 1994, Technical University of Hamburg–HarburgGermany, p. 413–418.
-
8)
-
Roy, B., Sussmann, B.: `Les problems d'ordonnancement avec contraintes disjonctives', SEMA, 1964, Montrougenote DS, .
-
9)
-
W.S. Gere
.
Heuristics in job shop scheduling.
Manage. Sci.
,
167 -
190
-
10)
-
A.H.G. Rinnooy Kan
.
(1976)
Machine scheduling problems: classification, complexity and computations.
-
11)
-
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: `Sequencing and scheduling: algorithms and complexity', BS-R8909, Report, 1989.
-
12)
-
M. Florian ,
P. Trepant ,
G. McMahon
.
An implicit enumeration algorithm for the machine sequencing problem.
Manage. Sci.
,
782 -
792
-
13)
-
S.K. Kim ,
K.T. Yeo ,
W.H. Lee
.
An expert neural network system for dynamic job shop scheduling.
Intern. J. Prod. Res.
,
1759 -
1773
-
14)
-
G.B. McMahon ,
M. Florian
.
On scheduling with ready times and due dates to minimize maximum lateness.
Oper. Res.
,
333 -
349
-
15)
-
W. Wang ,
P. Brunn
.
(1995)
Production scheduling and neural networks.
-
16)
-
J.N. Blackstone ,
D.T. Philips ,
C.L. Hogg
.
A state-of-the-art survey of dispatching rules for manufacturing jobshop operations.
Intern. J. Prod. Res.
,
27 -
45
-
17)
-
D.-C. Li ,
I.-S. She
.
Using unsupervised learning technologies to induce scheduling knowledgefor FMSs.
Intern. J. Prod. Res.
,
2187 -
2199
-
18)
-
J. Carlier ,
E. Pinson
.
An algorithm for solving the job shop problem.
Manage. Sci.
,
475 -
482
-
19)
-
Brucker, P., Jurisch, B., Sievers, B.: `A fast branch and bound algorithm for the job shop scheduling problem', 136, Report, 1991.
-
20)
-
S.S. Panwalkar ,
W. Iskander
.
A survey of scheduling rules.
Oper. Res.
,
45 -
61
-
21)
-
Yu.N. Sotskov ,
N.V. Shakhlevich
.
An adaptive algorithm for minimizing the makespan of processing jobsby sequential machines.
Izv. Akad. Nauk SSSR, Tekhn. Kibernet.
,
137 -
142
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-cta_19960089
Related content
content/journals/10.1049/ip-cta_19960089
pub_keyword,iet_inspecKeyword,pub_concept
6
6