lion6.bib

%% hal-00450238, version 1
%% http://hal.archives-ouvertes.fr/hal-00450238/en/
@inproceedings{Bouzarkouna2010,
    title = {{Investigating the Local-Meta-Model CMA-ES for Large Population Sizes}},
    author = {Bouzarkouna, Zyed and Auger, Anne and Ding, Didier Yu},
    abstract = {{For many real-life engineering optimization problems, the cost of one objective function evaluation can take several minutes or hours. In this context, a popular approach to reduce the number of function evaluations consists in building a (meta-)model of the function to be optimized using the points explored during the optimization process and replacing some (true) function evaluations by the function values given by the meta-model. In this paper, the local-meta-model CMA-ES (lmm-CMA) proposed by Kern et al. in 2006 coupling local quadratic meta-models with the Covariance Matrix Adaptation Evolution Strategy is investigated. The scaling of the algorithm with respect to the population size is analyzed and limitations of the approach for population sizes larger than the default one are shown. A new variant for deciding when the meta-model is accepted is proposed. The choice of the recombination type is also investigated to conclude that the weighted recombination is the most appropriate. Finally, this paper illustrates the influence of the different initial parameters on the convergence of the algorithm, for multimodal functions.}},
    booktitle = {{Proceedings of Applications of Evolutionary Computation, EvoApplicatons 2010: EvoCOMPLEX, EvoGAMES, EvoIASP, EvoINTELLIGENCE, EvoNUM, and EvoSTOC}},
    pages = {402-411},
    volume = {6024},
    editor = {Cecilia Di Chio},
    series = {Lecture Notes in Computer Science },
    year = {2010},
    month = Apr,
}
@article{Hutter2006,
author = {Hutter, Frank and Hamadi, Youssef and Hoos, Holger H and Leyton-brown, Kevin},
pages = {213--228},
title = {{Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms}},
year = {2006}
}
@article{Pfahringer2000,
author = {Pfahringer, Bernhard and Bensusan, Hilan},
journal = {on Machine Learning},
title = {{Meta-learning by landmarking various learning algorithms}},
year = {2000}
}
@article{Horvitz2001,
author = {Horvitz, E and Ruan, Y and Gomes, C and Kautz, H and Selman, B and Chickering, M},
doi = {10.1016/S1571-0653(04)00335-X},
issn = {15710653},
journal = {Electronic Notes in Discrete Mathematics},
month = jun,
pages = {376--391},
title = {{A Bayesian Approach to Tackling Hard Computational Problems (Preliminary Report)☆}},
volume = {9},
year = {2001}
}
@article{Shahzad2010,
author = {Shahzad, A and Mebarki, N},
journal = {Operations Research},
keywords = {data mining,job-shop scheduling,priority dispatching rules,simulation},
title = {{Discovering dispatching rules for job shop scheduling problem through data minging}},
year = {2010}
}
@article{Smith-Miles2009,
author = {Smith-Miles, K and James, R and Giffin, J},
journal = {Learning and Intelligent},
keywords = {algorithm selection,heuristics,knowledge discovery,performance prediction,scheduling,self-organizing map},
pages = {89--103},
title = {{A knowledge discovery approach to understanding relationships between scheduling problem structure and heuristic performance}},
year = {2009}
}
@article{Alanzi2006,
author = {Al-Anzi, FS and Sotskov, YN and Allahverdi, A},
doi = {10.1016/j.amc.2006.04.063},
issn = {00963003},
journal = {Applied mathematics and},
keywords = {branch and bound,job shop,mixed graph coloring,scheduling,total completion time},
month = nov,
number = {2},
pages = {1137--1148},
title = {{Using mixed graph coloring to minimize total completion time in job shop scheduling}},
volume = {182},
year = {2006}
}
@article{Panwalkar1977a,
author = {Panwalkar, S.S. and Iskander, W.},
doi = {10.1287/opre.25.1.45},
file = {:home/hei2/Documents/Literature/Mendeley/Panwalkar, Iskander\_1977\_A Survey of Scheduling Rules.pdf:pdf},
issn = {0030-364X},
journal = {Operations Research},
keywords = {JSP,JSP features},
mendeley-tags = {JSP,JSP features},
month = jan,
number = {1},
pages = {45--61},
title = {{A Survey of Scheduling Rules}},
url = {http://www.jstor.org/stable/169546},
volume = {25},
year = {1977}
}
@misc{gurobi,
    address = {Houston, Texas},
    author = {Gu, Zonghao and Rothberg, Edward and Bixby, Robert},
    howpublished = {software},
    keywords = {software},
    month = April,
    publisher = {Gurobi Optimization, Inc.},
    title = {{Gurobi Optimizer Version 4.5.2}},
    year = {2011},
    url = {http://www.gurobi.com/}
}
@inproceedings{Ingimundardottir2010,
author = {Ingimundardottir, Helga and Runarsson, Thomas Philip},
booktitle = {Learning and Intelligent Optimization, 5th International Conference, LION 5},
editor = {{Coello Coello}, Carlos A.},
title = {{ Supervised Learning Linear Priority Dispatch Rules for Job-Shop Scheduling}},
url = {http://lion.disi.unitn.it/intelligent-optimization//LION5/papers/lion5\_submission\_89.pdf},
series = {Lecture Notes in Computer Science },
year = {2010}
}
@inproceedings{Smith-miles2010,
author = {Smith-miles, Kate and Lopes, Leo},
booktitle = {Learning and Intelligent Optimization, 5th International Conference, LION 5},
editor = {{Coello Coello}, Carlos A.},
title = {{Generalising Algorithm Performance in Instance Space: A timetabling case study}},
url = {http://lion.disi.unitn.it/intelligent-optimization//LION5/papers/lion5\_submission\_42.pdf},
series = {Lecture Notes in Computer Science },
year = {2010}
}
@article{Corne2011,
author = {Corne, David and Reynolds, Alan},
file = {:home/hei2/Documents/Literature/Mendeley/Corne, Reynolds\_2011\_Optimisation and generalisation footprints in instance space.pdf:pdf},
journal = {Parallel Problem Solving from Nature, PPSN XI},
pages = {22--31},
title = {{Optimisation and generalisation: footprints in instance space}},
url = {http://www.springerlink.com/index/G02137102M8KN205.pdf},
series = {Lecture Notes in Computer Science },
year = {2011}
}
@article{WoMa97:tec,
author = {Wolpert, D.\~{}H. and Macready, W.\~{}G.},
journal = {IEEE Transactions on Evolutionary Computation},
number = {1},
pages = {67--82},
title = {{No free lunch theorems for optimization}},
volume = {1},
year = {1997}
}
@article{Rice1976,
  author    = {John R. Rice},
  title     = {The Algorithm Selection Problem},
  journal   = {Advances in Computers},
  volume    = {15},
  year      = {1976},
  pages     = {65-118},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}











@article{Malik2007,
author = {Malik, Abid M. and Russell, Tyrel and Chase, Michael and Beek, Peter},
doi = {10.1007/s10732-007-9051-1},
file = {:home/hei2/Documents/Literature/Mendeley/Malik et al.\_2007\_Learning heuristics for basic block instruction scheduling.pdf:pdf},
issn = {1381-1231},
journal = {Journal of Heuristics},
keywords = {instruction scheduling,list scheduling heuristics,machine learning},
month = oct,
number = {6},
pages = {549--569},
title = {{Learning heuristics for basic block instruction scheduling}},
url = {http://www.springerlink.com/index/10.1007/s10732-007-9051-1},
volume = {14},
year = {2007}
}
@article{Li2005,
author = {Li, Xiaonan and Olafsson, Sigurdur},
doi = {10.1007/s10951-005-4781-0},
file = {:home/hei2/Documents/Literature/Mendeley/Li, Olafsson\_2005\_Discovering Dispatching Rules Using Data Mining.pdf:pdf},
issn = {1094-6136},
journal = {Journal of Scheduling},
keywords = {data mining,decision trees,dispatching rules,scheduling},
month = dec,
number = {6},
pages = {515--527},
title = {{Discovering Dispatching Rules Using Data Mining}},
url = {http://www.springerlink.com/index/10.1007/s10951-005-4781-0},
volume = {8},
year = {2005}
}
@article{Tay2008,
author = {Tay, J and Ho, N},
doi = {10.1016/j.cie.2007.08.008},
file = {:home/hei2/Documents/Literature/Mendeley/Tay, Ho\_2008\_Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems.pdf:pdf},
issn = {03608352},
journal = {Computers \& Industrial Engineering},
keywords = {dispatching rules,flexible job shop,genetic programming,production scheduling},
month = apr,
number = {3},
pages = {453--473},
title = {{Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems}},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0360835207002008},
volume = {54},
year = {2008}
}
@inproceedings{Dietterich1995,
address = {San Francisco, California},
annote = {type: SSPP - space shuttle payload processing

        
obj. min makespan

        
Prev.work: iterative repair based scheduling procedure

        
Now:  TD(lambda) learning. Start with a relaxed problem, each task is scheduled as early as temporal partial order will permit. Resource constraints are IGNORED and are assigned randomnly to resource pools. <- Critical path, called s0

        
Two possible operators: MOVE (to a later or earlier date) and REASSIGN POOL (not applicable in our study - this is for flexible job shop scheduling, fJSP)

        
          
Learning policies: 
* small penalty for each scheduling action (reassign-pool/move) to encourage actions that quickly find good schedules
* -RDF(s',s0) : resource dilation factor, is an independant scale of the length of a schedule. Only for states s' that are free of violations. Encourage short final schedules.

        
          
Misc.
* RUI(i,t) is the resource utilization index for resource of type i (machine i) at time t. Either is 1 or a the fraction of overallocation.
* TRUI - total resource utilization index for a schedule of length l, TRUI = sum\_(i=1)\^{}n sum\_(t=1)\^{}l RUI(i,t)
* RDF(s,s0) = TRUI(s)/TRUI(s0)
--> Crude measure of the difficulty of the scheduling problem. Used to normalize the final schedule length to produce resource dilation factor.

        
          
Features:
* Mean and standard dev. of free pool capacity for bottleneck pools. Research show that only specific resource types (here: special machines) become major bottlenecks. For each bottleneck pool, the number of unallocated units (the free capacity) is measured over the whole schedule period
* Mean and standard dev. of slacks. We measure the minimum and average slack of each task, and their standard dev.
* Modified RDF. Resource dilation factor, is an independant scale of the length of a schedule. The numerator of the modified RDF is computed using the capacity and allocation of individual resource pools rather than resource types.

        
Not directly applicable:
* Over allocation index. Total number of units of over allocation resources in the current schedule diveded by the total number of units of over allocated resources in the starting schedule
* Percentage of windows in violation. A window is the maximal period of time during which the set ot currently scheduled tasks does not change. A schedule can be segmented into sequences of windows. We compute the percentage of windows that contain a constraint violation. We also find the earliest window that contains a constraint violation and compthe the percentage of the following 9 windows that have violations. 
* First violated window index (normalized).
* Percentage of windows in violation that can be resolved by pool reassignment. If the resources were not subdivided into pools the resource requirements could be met.
* Percentage of time units in violation. Over whole schedule period.

        
          
Synthetic jobs:
* total of n=20 jobs
* each job as random number of tasks, m=6...10 (large problems m=15..20)
* temporal contraints randomly generated among the tasks so that approx. 60\% of all possible pairwise precedence contraints are asserted
* Two types of resources. Each resource has two pools. One with capacity of 6 units, other of 8 units.
* Resource requirements are randomnly assigned to each task uniformly from the 0-6 units, for each resource types.
* 50 training sets, 50 test sets.},
author = {Zhang, Wei and Dietterich, Thomas G.},
booktitle = {Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence},
file = {:home/hei2/Documents/Literature/Mendeley/Zhang, Dietterich\_1995\_A Reinforcement Learning Approach to Job-shop Scheduling.pdf:pdf},
pages = {1114--1120},
publisher = {Morgan-Kaufmann},
title = {{A Reinforcement Learning Approach to Job-shop Scheduling}},
year = {1995}
}
@article{Garey1976,
author = {Garey, MR and Johnson, DS and Sethi, R.},
doi = {10.1287/moor.1.2.117},
file = {:home/hei2/Documents/Literature/Mendeley/Garey, Johnson, Sethi\_1976\_The complexity of flowshop and jobshop scheduling.pdf:pdf},
issn = {0364-765X},
journal = {Mathematics of Operations Research},
month = may,
number = {2},
pages = {117--129},
title = {{The complexity of flowshop and jobshop scheduling}},
url = {http://www.jstor.org/stable/3689278},
volume = {1},
year = {1976}
}