From pat@cs.strath.ac.uk Tue Dec 21 17:52:52 EST 1993
Article: 20023 of comp.ai
Xref: glinda.oz.cs.cmu.edu comp.ai:20023
Path: honeydew.srv.cs.cmu.edu!nntp.club.cc.cmu.edu!news.mic.ucla.edu!library.ucla.edu!agate!doc.ic.ac.uk!warwick!str-ccsun!strath-cs!strath-cs!not-for-mail
From: pat@cs.strath.ac.uk (Patrick Prosser)
Newsgroups: comp.ai
Subject: Re: Scheduling
Date: 21 Dec 1993 11:04:52 -0000
Organization: Comp. Sci. Dept., Strathclyde Univ., Glasgow, Scotland.
Lines: 378
Message-ID: <2f6l8k$39t@kelvin-02.cs.strath.ac.uk>
References: <we31602-161293153105@igwefpmc203.vub.ac.be> <CI7y67.t9@eng_ser1.ie.cuhk.hk> <1993Dec20.084933.20606@ilog.fr>
NNTP-Posting-Host: kelvin-02.cs.strath.ac.uk

In article <1993Dec20.084933.20606@ilog.fr> lepape@ilog.UUCP (Claude Le Pape) writes:
>
>> I am currently studying a scheduling problem for my thesis, but litterature
>> on the subject seems hard to find. Except for the Train scheduling program
>> for the belgian railways, I don't have much to go on. So, if you happen to
>> see a paper or article about scheduling, could you either tell me where to
>> find it or have it mailed to me?
>>
>> Yves Van Beethoven
>
>Here is a set of references I recently provided for a tutorial on
>constraint-based scheduling. Naturally, this set is quite biased toward
>the topic of interest to me, i.e. generative constraint-based scheduling.
>Let us hope someone will post a complement on iterative techniques for
>scheduling!
>

What follows is a bib.tex on papers that I think are relevant to scheduling,
and again is biased :-) It's got references on intelligent scheduling systems,
genetic algorithms, simulated annealing, tabu search, and the repair algorithm.
So, you'll find some of the iterative techniques. Also references to csp and some of
the most recent studies on problems (I think these hold great promise for us
schedulers)

Patrick
 __________________________________________________________________________
| Patrick Prosser, Department of Computer Science.                         |
| University of Strathclyde, Glasgow G1 1XH, Scotland.                     |
| email: pat@cs.strath.ac.uk  phone: +44 41 552 4400 fax: +44 41 552 5330  |
 --------------------------------------------------------------------------

~~~~~~~~~~~~~~~~~~~~~ Save and latex it ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\documentstyle [a4my]{article}
\input epsf
\begin{document}
\begin{thebibliography}{}
\bibitem [1]{}
ADENZO-DIAZ, B.:
'Restricted neighborhood in the tabu search for the flowshop problem',
{\em European Journal of Operational Research,} 
62 (1992) 27-37
\bibitem [2]{}
ADORF, H.M., and JOHNSTON, M.D.:
'A discrete stochastic neural network for constraint satisfaction
problems', {\em Proc International Joint Conference on Neural Networks} 917-924 1990
\bibitem [3]{}
BERRY, P.M.:
'The PCP: a predictive model for satisfying conflicting objectives in scheduling problems',
{\em Artificial Intelligence in Engineering,} 
7(4) 227-242, 1992
\bibitem [4]{}
BRUNS, R.:
'Direct chromosome representation and advanced genetic operators for
production scheduling', {\em Proc ICGA-93}
\bibitem [5]{}
BRUNS, R.:
'Knowledge-augmented genetic algorithms for production scheduling',
{\em IJCAI-93 Workshop on Knowledge-based Production Planning, Scheduling, and Control,} 49-58
\bibitem [6]{}
BURKE, P. and PROSSER, P.:
'A distributed asynchronous system for predictive and reactive scheduling',
{\em Artificial Intelligence in Engineering} 6(3) 106-124, July 1991
\bibitem [7]{}
CLEARWATER, S.H., HUBERMAN, B.A. and HOGG, T.:
'Cooperative solution of constraint satisfaction problems',
{\em Science,} 254:1181-1183
\bibitem [8]{}
CHEESEMAN, P., KANEFSKY, B., and TAYLOR, W.M.:
'Where the {\em really} hard problems are',
{\em Proc IJCAI-91,}
331-337
\bibitem [9]{}
CLEVELAND, G.A. and SMITH, S.F.:
'Using genetic algorithms to schedule flow shop releases',
{\em Proc ICGA-89} 160-169
\bibitem [10]{}
COLLINOT, A., LEPAPE, C. and PINOTEAU, C.:
'SONIA: A knowledge based scheduling system',
{\em Artificial Intelligence in Engineering} 3(2) 86-94, April 1988
\bibitem [11]{}
COOK, S.A.:
'The complexity of theorm-proving procedures',
{\em Proc of the 3d Annual ACM Symposium on Theory of Computing} 151-158
\bibitem [12]{}
COOK, S.A.:
'An overview of computational complexity',
{\em CACM} 26(6) 401-408
\bibitem [13]{}
CORKILL, D.:
'Blackboard systems', {\em AI Expert} 6(9) 40-47 September 1991
\bibitem [14]{}
DAVIS, L.:
'Job shop scheduling with genetic algorithms',
{\em Proc ICGA-85} 136-140
\bibitem [15]{}
DAVIS, R. and SMITH, R.G.:
'Negotiation as a metaphor for distributed problem solving',
{\em Artif Intell} 20(1) 63-109 
\bibitem [16]{}
DECHTER, R. and PEARL, J.:
'Network based heuristics for constraint satisfaction problems',
{\em Artif Intell,} 34(1988) 1-38
\bibitem [17]{}
ELLEBY, P., FARGHER, H.E. and ADDIS, T.R.:
'Reactive constrained-based scheduling',
in {Colloquium on Artificial Intelligence in Planning of Production Control,}
IEE Computing and Control Division, London, May 1988
\bibitem [18]{}
FOX, M.S.:
M.S. Fox, An organisational view of distributed systems,
{\em IEEE Transactions on Systems, Man, and Cybernetics,} SMC-11(1) 70-80 1981
\bibitem [19]{}
FOX, M.S.:
'Constraint-directed search: A case study of job shop scheduling',
Technical Report CMU-RI-TR-83-22, Robotics Institute, Carnegie Mellon University.
\bibitem [20]{}
FOX M.S., SADEH, N., 'Why is scheduling difficult? A csp perspective.'
{\em Proc ECAI-90} 754-767
\bibitem [21]{}
FOX, M.S., SADEH, N. and BAYKAN, C.:
'Constrained heuristic search',
{\em Proc IJCAI-89,} 309-315
\bibitem [22]{}
GAREY, M.R. and JOHNSON, D.S.:
'Computers and Intractability: A guide to the theory of NP-Completness',
W.H. Freeman and Company, ISBN 0-7167-1045-5
\bibitem [23]{}
GEELEN, P.A.:
'Dual viewpoint heuristics for binary constraint satisfaction problems',
{\em Proc ECAI-92,} 31-35
\bibitem [24]{}
GINSBERG, M.L.:
'Dynamic Backtracking', 
{\em Journal of Artificial Intelligence Research (JAIR)} 1(1993) 25-46
\bibitem [25]{}
GLOVER, F:
'Tabu Search - Part I',
{\em ORSA Journal on Computing,} 1(3) Summer 1989 190-206
\bibitem [26]{}
GLOVER, F:
'Tabu Search - Part II', {\em ORSA Journal on Computing,} 2(1) Winter 1990 4-32
\bibitem [27]{}
GLOVER, F:
'Tabu Search', {\em Annals of Operations Research,} 41
\bibitem [28]{}
GLOVER, F, and GREENBERG, H.J.:
'New approaches for heuristic search: A bilateral linkage with artificial intelligence', 
{\em European Journal of Operational Research,} 39 (1989) 119-130
\bibitem [29]{}
HARALICK, R.M. and ELLIOTT, G.L.:
'Increasing tree search efficiency for constraint satisfaction problems',
{\em Artif Intell,} 14 (1980) 263-313
\bibitem [30]{}
HADAVI, K., HSU, W-L., CHEN, T. and LEE, C-N.:
'An architecture for real-time distributed scheduling',
{\em AI Magazine} 14(3) 46-56, Fall 1992
\bibitem [31]{}
HART, P.E., NILSSON, N.J., and RAPHAEL, B.:
'A formal basis for the heuristic determination of minimum cost paths',
{\em IEEE Transactions on Systems, Science and Cybernetics,} 
SSC-4(2), 100-107, 1968
\bibitem [32]{}
HAYES-ROTH, B.:
'A blackboard architecture for control',
{\em Artif Intell} 26(3) 251-321
\bibitem [33]{}
HOGG, T. and WILLIAMS, C.P.:
'Solving really hard problems with cooperative search',
{\em Proc AAAI-93,} 
\bibitem [34]{}
HOLLAND, J.H.:
'Adaption in natural and artificial systems',
{\em University of Michigan Press,} Ann Arbor, MI
\bibitem [35]{}
HOLLAND, J.H.:
'Genetic Algorithims',
{\em Scientific American} July 1992, 44-50
\bibitem [36]{}
KELLEHER, G. and van der Gaag, L.:
'The LazyRMS: avoiding work in the ATMS',
{\em Computational Intelligence} 9(3) 239-253
\bibitem [37]{}
KENG, N. and YUN, D.Y.Y.:
'A planning/scheduling methodology for the constrained resource problem',
{\em Proc IJCAI-89,} 998-1003
\bibitem [38]{}
KIRKPATRICK, S. GELATT jr, C.D. and VECCHI, M.P.:
'Optimization by simulated annealing',
{\em Science,} 220, 671-680
\bibitem [39]{}
KUCHENHOFF, V.:
'Novel search and constraints - an integration',
Working paper {\em ECRC-CORE-93-9}, European Computer-Industry Research Centre.
\bibitem [40]{}
LAGUNA, M., WESLEY BARNES, J., and GLOVER, F.:
'Tabu search methods for a single machine scheduling problem',
{\em Journal of Intelligent Manufacturing,} 
(1991) 2, 63-74
\bibitem [41]{}
LAGUNA, M., WESLEY BARNES, J., and GLOVER, F.:
'Intelligent scheduling with tabu search: an application to jobs
with linear delay penalties and sequence-dependant setup costs and times',
{\em Applied Intelligence,} 
3(2) 159-172 1993
\bibitem [42]{}
LAGUNA, M. and GLOVER, F.:
'Integrating target analysis and tabu search for improved scheduling systems',
{\em Expert Systems with Applications,} 6(3) 287-297 1993
\bibitem [43]{}
LAWLER, E.L., LENSTRA, J.K., RINNOY KAN, A.H.G. and SHMOYS, D.B.:
'The Traveling Salesman Problem: A guided tour of combinatorial optimization',
{\em Wiley-Interscience Publication,} 
ISBN 0 471 90413 9
\bibitem [44]{}
LAWTON, G.:
'Genetic algorithms for schedule optimisation',
{\em AI Expert} 7(5) 22-27
\bibitem [45]{}
LEPAPE, C. and SAUVE, B.:
'SOJA: an expert system for workshop daily planning',
{\em Proc Avignon-85} 849-867
\bibitem [46]{}
LESSER, V.R. and CORKILL, D.:
'Functionally accurate, cooperative distributed systems',
{\em IEEE Transactions on Systems Man and Cybernetics} SMC-11(1) 81-96 January 1981
\bibitem [47]{}
McKENZIE, L.W.:
'Turnpike Theory', {\em Econometrica} 44(5) 841-865 1976
\bibitem [48]{}
MAHANTI, A. and DANIELS, C.J.:
'A SIMD approach to parallel heuristic search', {\em Artif Intell} 60(2) 243-282
\bibitem [49]{}
MALEK, M., GURUSWAMY, M., PANDYA, M. and OWENS, H.:
'Serial and parallel simulated annealing and tabu search algorithms for the 
travelling salesman problem', {\em Annals of Operations Research,} 21 (1989) 59-84
\bibitem [50]{}
MINTON, S., JOHNSTON, M.D., PHILIPS, A.B., and LAIRD, P.:
'Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems',
{\em Artif Intell} 58(1-3) December 1992, 161-206
\bibitem [51]{}
MITCHELL, D., SELMAN, B. and LEVESQUE, H.:
'Hard and easy distributions of SAT problems',
{\em Proc AAAI-92,} 459-465
\bibitem [52]{}
MORGADO, E.M. and MARTINS, J.P.:
'An AI based approach to crew scheduling',
{\em Proc CAIA-93} 71-77
\bibitem [53]{}
MOTT, D.H., CUNNINGHAM, J., KELLEHER, G. and GADSEN, J.A.:
'Constraint-based reasoning for generating naval flying programmes',
{\em Expert Systems} 5(3) 226-246 August 1988
\bibitem [54]{}
MULLER, C., MAGILL, E.H., PROSSER, P., and SMITH, D.G.:
'Stochastic and local techniques for resource allocation problems', {\em Proc Avignon-93} 635-644
\bibitem [55]{}
MUSICK, R. and RUSSELL, S.:
'How long will it take',
in {\em Proc AAAI-92} 466-471
\bibitem [56]{}
MUSCETTOLA, N.:
'Scheduling by iterative partition of bottleneck conflicts', {\em Proc CAIA-93} 49-55
\bibitem [57]{}
NAKANO, R.:
'Conventional genetic algorithms for job shop problems',
{\em Proc ICGA-91} 474-479
\bibitem [58]{}
NII, H.P.:
'Blackboard systems: the blackboard model of problem solving and the evolution of blackboard 
architectures', {\em AI Magazine} 7(2) 38-53 Summer 1986
\bibitem [59]{}
NILSSON, N.J.:
{\em Principles of Artificial Intelligence}, Springer-Verlag, ISBN 3-540-11340-1
\bibitem [60]{}
van Dyke PARUNAK, H., IRISH, W., KINDRICK, J., and LOZO, P.W.:
'Fractal actors for distributed manufacturing',
{\em Proc CAIA-85} 653-660
\bibitem [61]{}
van Dyke PARUNAK, H.:
'Manufacturing experience with the contract net',
in {\em Distributed Artificial Intelligence I} M.N. Huns (ed), Morgan Kaufmann Publishers, 1987, 285-310
\bibitem [62]{}
OW, P.S. and SMITH, S.F.:
'Viewing scheduling as an opportunistic problem solving process',
{\em Annals of Operations Research,} 12:85-108, 1988
\bibitem [63]{}
PERRY, E.L.:
'Solution of time constrained scheduling problems with parallel tabu search',
{\em Proc 1990 DARPA Workshop, Innovative approaches to planning, scheduling, and control,} 
231-239
\bibitem [64]{}
PROSSER, P.:
'A hybrid genetic algorithm for pallet loading',
{\em Proc ECAI-88} 159-164
\bibitem [65]{}
PROSSER, P.:
'A reactive scheduling agent', {\em Proc IJCAI-89} 1004-1009
\bibitem [66]{}
PROSSER, P.:
'Hybrid algorithms for the constraint satisfaction problem',
{\em Computational Intelligence} 9(3) 268-299
\bibitem [67]{}
PROSSER, P.:
'BM+BJ=BMJ', {\em Proc CAIA-93} 257-262
\bibitem [68]{}
PROSSER, P.:
'Domain filtering can degrade intelligent backjumping search',
{\em Proc IJCAI-93} 262-267
\bibitem [69]{}
PROSSER, P.:
'Scheduling as a constraint satisfaction problem: theory and practice',
in {\em Scheduling of Production Processes} J. Dorn and K.A. Froeschl (eds),
Ellis Horwood, 22-30, 1993
\bibitem [70]{}
PROSSER, P., CONWAY, C., and MULLER, C.:
'A constraint maintenance system for the distributed resource allocation problem',
{\em ISE} 1(1) 76-83 Autumn 1992
\bibitem [71]{}
ROBUSTE, F., DAGANZO, C.F., and SOULEYRETTE, R.S.:
'Implementing vehicle routing models',
{\em Transportation Research} 24B(4) 263-286
\bibitem [72]{}
SADEH, N.:
'Look-ahead techniques for micro-opportunistic job shop scheduling',
Technical Report CMU-CS-91-102, March 1991,
School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
\bibitem [73]{}
SADEH, N.:
'MICRO-BOSS: a micro-opportunistic factory scheduler',
{\em Expert Systems with Applications,} 
6(3) July-September, 377-392, 1993
\bibitem [74]{}
SELMAN, B., LEVESQUE, H., and MITCHELL, D.:
'A new method for solving hard satisfiability problems',
{\em Proc AAAI-92,} 440-446
\bibitem [75]{}
SELMAN, B., and KAUTZ, H.A.:
'An empirical study of greedy local search for satisfiability testing',
{\em Proc AAAI-93}
\bibitem [76]{}
SMITH, D.:
'Bin packing with adaptive search', 
{\em Proc ICGA-85} 202-207
\bibitem [77]{}
SMITH, S.F., FOX, M.S., and OW, P.S.:
'Constructing and maintaining detailed production plans: Investigations into the
development of knowledge based factory scheduling systems',
{\em AI Magazine} 7(4) 45-61 Fall 1987
\bibitem [78]{}
SYSWERDA, G. and PALMUCCI, J.:
'The application of genetic algorithms to resource scheduling',
{\em Proc ICGA-91} 502-508
\bibitem [79]{}
val LAARHOVEN, P.J.M, AARTS, E.H.L, and LENSTRA, J.K.:
'Job shop scheduling by simulated annealing',
{\em Operations Research,} 40(1) January-February 1992, 113-125
\bibitem [80]{}
THANGIAH, S.R., NYGARD, K.E., and JUELL, P.L.:
'GIDEON: a genetic algorithm system for vehicle routing with time windows',
{\em Proc CAIA-91} 322-328
\bibitem [81]{}
WIDMER, M.:
'Job shop scheduling with tooling constraints: a tabu search approach',
{\em Journal of the Operational Research Society,} 
42 (1) 75-82, 1991
\bibitem [82]{}
WILLIAMS, C.P. and HOGG, T.:
'Extending deep structure',
{\em Proc AAAI-93}
\bibitem [83]{}
WILLIAMS, C.P. and HOGG, T.:
'The typicality of phase transitions in search',
{\em Computational Intelligence,} 9(3), 221-238
\bibitem [84]{}
ZWEBEN, M., DAVIS, E., DAUN, B., DRASCHER, E., DEALE, M.,  and ESKEY, M.:
'Learning to improve constraint based scheduling',
{\em Artif Intell} 58(1-3) 271-296 December 1992
\end{thebibliography}
\end{document}


