biblio.bib

@article{Asmuni,
author = {Asmuni, Hishammudin and Burke, K},
file = {:home/hei2/Documents/Literature/Mendeley/Asmuni, Burke\_Unknown\_An Investigation of Fuzzy Multiple Heuristic Orderings in the Construction of University Examination Timetables.pdf:pdf},
journal = {Science},
number = {April 2008},
title = {{An Investigation of Fuzzy Multiple Heuristic Orderings in the Construction of University Examination Timetables}}
}
@article{Burke2006,
author = {Burke, EK and Petrovic, Sanja and Qu, Rong},
file = {:home/hei2/Documents/Literature/Mendeley/Burke, Petrovic, Qu\_2006\_Case-based heuristic selection for timetabling problems.pdf:pdf},
journal = {Journal of Scheduling},
keywords = {case based reasoning,course timetabling,discovery,exam timetabling,graph heuristics,knowledge,meta-heuristics},
number = {2},
pages = {115--132},
title = {{Case-based heuristic selection for timetabling problems}},
url = {http://www.springerlink.com/index/U384473118WL6213.pdf},
volume = {9},
year = {2006}
}
@article{Jain1999,
author = {Jain, A.S. and Meeran, S.},
doi = {10.1016/S0377-2217(98)00113-1},
file = {:home/hei2/Documents/Literature/Mendeley/Jain, Meeran\_1999\_Deterministic job-shop scheduling Past, present and future.pdf:pdf},
issn = {03772217},
journal = {European Journal of Operational Research},
keywords = {computational study,job-shop,review,scheduling theory},
month = mar,
number = {2},
pages = {390--434},
title = {{Deterministic job-shop scheduling: Past, present and future}},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0377221798001131},
volume = {113},
year = {1999}
}
@article{glpk,
author = {Makhorin, A},
file = {:home/hei2/Documents/Literature/Mendeley/Makhorin\_2009\_GNU linear programming kit.pdf:pdf},
journal = {Moscow Aviation Institute, Moscow, Russia},
number = {May},
title = {{GNU linear programming kit}},
url = {http://www.citeulike.org/user/pohlmaximilian/article/5651691},
volume = {38},
year = {2009},
note= {Software available at \url{http://www.gnu.org/software/glpk/glpk.html}}
}
@article{newtontrustregion,
author = {Lin, Chih-jen and Weng, Ruby C},
file = {:home/hei2/Documents/Literature/Mendeley/Lin, Weng\_2008\_Trust Region Newton Method for Large-Scale Logistic Regression.pdf:pdf},
journal = {Journal of Machine Learning Research},
keywords = {conjugate gradient,logistic regression,newton method,support,trust region},
pages = {627--650},
title = {{Trust Region Newton Method for Large-Scale Logistic Regression}},
volume = {9},
year = {2008}
}
@article{Herbrich00,
author = {Herbrich, Ralf and Graepel, T and Obermayer, K},
file = {:home/hei2/Documents/Literature/Mendeley/Herbrich, Graepel, Obermayer\_2000\_Large margin rank boundaries for ordinal regression.pdf:pdf},
journal = {Advances in Large Margin Classifier},
pages = {115--132},
title = {{Large margin rank boundaries for ordinal regression}},
url = {http://www.citeulike.org/user/hazen/article/5372764},
year = {2000}
}
@inproceedings{joachims02,
author = {Joachims, T},
booktitle = {Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD)},
file = {:home/hei2/Documents/Literature/Mendeley/Joachims\_2002\_Optimizing Search Engines Using Clickthrough Data.pdf:pdf},
organization = {ACM},
title = {{Optimizing Search Engines Using Clickthrough Data}},
year = {2002}
}

@inproceedings{Ru06:PPSN,
author = {Runarsson, T P},
booktitle = {Parallel Problem Solving from Nature IX (PPSN-2006)},
file = {:home/hei2/Documents/Literature/Mendeley/Runarsson\_Unknown\_Ordinal Regression in Evolutionary Computation.pdf:pdf},
pages = {1048--1057},
title = {Ordinal Regression in Evolutionary Computation},
year = {2006}
}

@article{Boyan2002a,
abstract = {TD($\lambda$) is a popular family of algorithms for approximate policy evaluation in large MDPs. TD($\lambda$) works by incrementally updating the value function after each observed transition. It has two major drawbacks: it maymake inefficient use of data, and it requires the user to manually tune a stepsize schedule for good performance. For the case of linear value function approximations and $\lambda$=0, the Least-Squares TD (LSTD) algorithm of Bradtke and Barto (1996, Machine learning, 22:1–3, 33–57) eliminates all stepsize parameters and improves data efficiency. This paper updates Bradtke and Barto’s work in three significant ways. First, it presents a simpler derivation of the LSTD algorithm. Second, it generalizes from $\lambda$=0 to arbitrary values of $\lambda$; at the extreme of $\lambda$=1, the resulting new algorithm is shown to be a practical, incremental formulation of supervised linear regression. Third, it presents a novel and intuitive interpretation of LSTD as a model-based reinforcement learning technique.},
annote = {Small number of features -> LSTD($\lambda$)
Large number of features -> TD($\lambda$)},
author = {Boyan, J.A.},
file = {:home/hei2/Documents/Literature/Mendeley//Boyan\_2002\_Technical update Least-squares temporal difference learning.pdf:pdf},
journal = {Machine Learning},
keywords = {Reinforcement learning,least-squares methods,linear,linear least squares methods,reinforcement learning,temporal difference learning,value function approximation},
mendeley-tags = {Reinforcement learning,linear least squares methods,temporal difference learning,value function approximation},
number = {2},
pages = {233--246},
publisher = {Springer},
title = {{Technical update: Least-squares temporal difference learning}},
url = {http://www.springerlink.com/index/H40XPNJBHXXMN5HV.pdf},
volume = {49},
year = {2002}
}
@article{Burstall1966,
author = {Burstall, RM},
file = {:home/hei2/Documents/Literature/Mendeley/Burstall\_1966\_A heuristic method for a job-scheduling problem.pdf:pdf},
journal = {OR},
number = {3},
pages = {291--304},
publisher = {Pergamon Press},
title = {{A heuristic method for a job-scheduling problem}},
url = {http://www.jstor.org/stable/3006560},
volume = {17},
year = {1966}
}
@article{Chang1996a,
annote = {Policies for companies for setting due dates: due date tightness, instead of a particular set date.

        
Dispatching rules, features for JSP:
1) FIFO - first in, first out
        
2) SPT - shortest imminent processing time
        
3) LST - least slack time
        
4) EDD - earliest due date
        
5) ODD - earliest operation due date, set by the total work (TWK) operation due-date rule
6) MOD - modified operation due date, determined by max(original operation due date, its early finish time)},
author = {Chang, F.C.R.},
file = {:home/hei2/Documents/Literature/Mendeley/Chang\_1996\_A study of due-date assignment rules with constrained tightness in a dynamic job shop.pdf:pdf},
journal = {Computers \& Industrial Engineering},
keywords = {dispatching rule,due-date assignment rule,dynamic job shop,scheduling,simulation},
number = {1-2},
pages = {205--208},
publisher = {Elsevier},
title = {{A study of due-date assignment rules with constrained tightness in a dynamic job shop}},
url = {http://linkinghub.elsevier.com/retrieve/pii/036083529600112X},
volume = {31},
year = {1996}
}
@article{Davis1975a,
annote = {obj. min makespan

        
comparison between heuristics and optimum solutions

        

        
Types of heuristics:

        MINSLK - minimum job slack
        

        RSM - resource scheduling method. Activity priority is calculated as the increase in project duration resulting when activity j follows activity i, called dij, and comparison is made on a pairwise basis among all activities in the conflict set. 

        LFT - minimum late finish time
        

        GRD - greatest resource demand, time consuming jobs get higher priority

        GRU - greatest resource utilisation, i.e. minimum idle resources

        SIO - shortest imminent operation, short jobs get signed first
          
MJP - most job possible. 
          
RAN - select jobs randomly
      },
author = {Davis, E. W. and Patterson, J. H.},
doi = {10.1287/mnsc.21.8.944},
file = {:home/hei2/Documents/Literature/Mendeley/Davis, Patterson\_1975\_A Comparison of Heuristic and Optimum Solutions in Resource-Constrained Project Scheduling.pdf:pdf},
issn = {0025-1909},
journal = {Management Science},
month = apr,
number = {8},
pages = {944--955},
title = {{A Comparison of Heuristic and Optimum Solutions in Resource-Constrained Project Scheduling}},
url = {http://mansci.journal.informs.org/cgi/doi/10.1287/mnsc.21.8.944},
volume = {21},
year = {1975}
}
@article{Drobouchevitch2000,
author = {Drobouchevitch, I},
doi = {10.1016/S0377-2217(99)00253-2},
file = {:home/hei2/Documents/Literature/Mendeley/Drobouchevitch\_2000\_Heuristics for the two-stage job shop scheduling problem with a bottleneck machine.pdf:pdf},
issn = {03772217},
journal = {European Journal of Operational Research},
keywords = {approximation algorithm,job shop scheduling,worst-case analysis},
month = jun,
number = {2},
pages = {229--240},
title = {{Heuristics for the two-stage job shop scheduling problem with a bottleneck machine}},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0377221799002532},
volume = {123},
year = {2000}
}
@article{Du1990,
author = {Du, J. and Leung, J. Y.-T.},
doi = {10.1287/moor.15.3.483},
file = {:home/hei2/Documents/Literature/Mendeley/Du, Leung\_1990\_Minimizing Total Tardiness on One Machine is NP-Hard.pdf:pdf},
issn = {0364-765X},
journal = {Mathematics of Operations Research},
month = aug,
number = {3},
pages = {483--495},
title = {{Minimizing Total Tardiness on One Machine is NP-Hard}},
url = {http://mor.journal.informs.org/cgi/doi/10.1287/moor.15.3.483},
volume = {15},
year = {1990}
}
@article{Gao2007,
annote = {Multiobjective:
* min makespan
* min maximal machine workload
* min total workload

        
bottleneck shifting},
author = {Gao, Jie and Gen, Mitsuo and Sun, Llinyan and Zhao, Xiaohui},
doi = {10.1016/j.cie.2007.04.010},
file = {:home/hei2/Documents/Literature/Mendeley/Gao et al.\_2007\_A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems☆.pdf:pdf},
issn = {03608352},
journal = {Computers \& Industrial Engineering},
keywords = {bottleneck shifting,flexible job shop scheduling,genetic algorithm,neighborhood structure,problem},
number = {1},
pages = {149--162},
title = {{A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems☆}},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0360835207000733},
volume = {53},
year = {2007}
}
@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}
}
@article{GereJr1966,
annote = {obj. min makespan

        
also 
* min tardiness
* min earliness

        
Remark: Dynamic problems added (new jobs admitted sporadically), which is often the case in real life examples.

        
Policies: 
* Priority, a smaller priority index gets served first

        
Priority rules:
1) Job slack (slack = due date - operation times)
2) Job slack per operation
3) Job slack ratio (job slack hours divided by hours remaining until the due date)
4) Modified job slack ratio, which takes machine loading into account to each operation time the expected delay associated with it
5) Length of next operatio. SIO-rule, shortest imminent operation
6) Length of next operation together with job slack ratio under certain circumstances
7) FIFO-rule, first come first served <- random
8) Random, e.g.
* Priority = due date - present time - processing hours remaining

        
Other features
* Number of operations left
* Operation times 
* Due dates
* Effectiveness: amount of tardiness of job completion

        
          
Dynamic rules take into account additional information not available to the static rule.
        

        

        
No one rule is robust enough to be superior to all of them. Therefore there are exceptions needed to the priority rule. Approaches:
1) Alternate operation. If a priority rule makes another job critical, then revoke the last operation and schedule the next operation on the critical job.
2) Look ahead. Check if there is a critical job in the not so distant future, if so, schedule that job first. Check its effect on other jobs.
3) Insert. If there is a long idle time on a machine before a look ahead job is due on that machine, then take the longest job that fits from the queue during that idle time.
4) Time-transcending schedule. Schedule jobs after their priority rating (not  directly their due date).
5) Subset of critical jobs. If critical jobs may utilise a machine for many consecutive hours; a non-critical job is forced to wait many hours at the machine, thereby becoming first critical and then late; if a critical job had been postponed a short time to permit scheduling the other job, then both would have been completed on time.
6) Re-do with adjusted due dates. If the heuristic still yields late jobs, then decrease the due date of the late job by its lateness and re-do the algorithm, and hope the boost in priority will yield a better schedule this time around.
7) Flexibility. Squeeze jobs in between that need to get done before other scheduled tasks where needed, latter tasks will be delayed slightly.
8) Manipulation. Jig-saw puzzle approach, if there is a gap on a machine try to move a (late) job up into it.},
author = {{Gere Jr}, W.S.},
file = {:home/hei2/Documents/Literature/Mendeley/Gere Jr\_1966\_Heuristics in Job Shop Scheduling.pdf:pdf},
journal = {Management Science},
keywords = {JSP,JSP features},
mendeley-tags = {JSP,JSP features},
number = {3},
pages = {167--190},
title = {{Heuristics in Job Shop Scheduling}},
url = {http://www.jstor.org/stable/2627860},
volume = {13},
year = {1966}
}
@article{Guinet1998a,
annote = {No dominant rule for JSP, but effective are e.g.
* MWKR - most work remaining
* SPT - shortest processing time
* LWKR - least work remaining

        
Lower bounds:
* LBJ = largest processing time of the jobs
* LBM = largest machine requirement

        
Reduction: Most problems in JSP are flow-shop problems, i.e. a lot of jobs use the machines in the same order },
author = {Guinet, Alain},
doi = {10.1016/S0377-2217(97)00129-X},
file = {:home/hei2/Documents/Literature/Mendeley//Guinet\_1998\_Reduction of job-shop problems to flow-shop problems with precedence constraints.pdf:pdf},
issn = {03772217},
journal = {European Journal of Operational Research},
keywords = {flow-shop,heuristics,job-shop,optimization,scheduling theory},
month = aug,
number = {1},
pages = {96--110},
title = {{Reduction of job-shop problems to flow-shop problems with precedence constraints}},
url = {http://linkinghub.elsevier.com/retrieve/pii/S037722179700129X},
volume = {109},
year = {1998}
}
@article{Hart2005,
author = {Hart, Emma and Ross, Peter and Corne, David},
doi = {10.1007/s10710-005-7580-7},
file = {:home/hei2/Documents/Literature/Mendeley/Hart, Ross, Corne\_2005\_Evolutionary Scheduling A Review.pdf:pdf},
issn = {1389-2576},
journal = {Genetic Programming and Evolvable Machines},
keywords = {evolutionary algorithms,scheduling},
month = jun,
number = {2},
pages = {191--220},
title = {{Evolutionary Scheduling: A Review}},
url = {http://www.springerlink.com/index/10.1007/s10710-005-7580-7},
volume = {6},
year = {2005}
}
@article{Hartmann2000,
author = {Hartmann, S},
doi = {10.1016/S0377-2217(99)00485-3},
file = {:home/hei2/Documents/Literature/Mendeley/Hartmann\_2000\_Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem.pdf:pdf},
issn = {03772217},
journal = {European Journal of Operational Research},
keywords = {experimental evaluation,heuristics,resource-constrained project scheduling},
month = dec,
number = {2},
pages = {394--407},
title = {{Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem}},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0377221799004853},
volume = {127},
year = {2000}
}
@article{Ho2007,
annote = {FJSP - In practice, the shopfloor setup typically consists of multiple copies of the most critical machines so that bottlenecks due to long operations or busy machines can be reduced.

        
Obj. min makespan

        
Features: 
* good traits <- for improvement
* bad traits <- to avoid 

        
Dynamic learning of schemas: Use k-nearest neighbor method (k-NN) to find the k  most similar solutions to a solution and classify the latter based on a majority vote. 
Therefore only update after k  generations.

        
Features:
* CDR - compsite dispatching rules
* FIFO - first in first out
* SPT - shortest processing time
* LPT - longest processing time},
author = {Ho, Nhu Binh and Tay, Joc Cing and Lai, Edmund M},
doi = {10.1016/j.ejor.2006.04.007},
file = {:home/hei2/Documents/Literature/Mendeley/Ho, Tay, Lai\_2007\_An effective architecture for learning and evolving flexible job-shop schedules.pdf:pdf},
journal = {European Journal Of Operational Research},
keywords = {composite dispatching rules,flexible job-shop problems,genetic algorithms,scheduling},
pages = {316--333},
title = {{An effective architecture for learning and evolving flexible job-shop schedules}},
volume = {179},
year = {2007}
}
@article{Jain1999,
author = {Jain, a},
doi = {10.1016/S0377-2217(98)00113-1},
file = {:home/hei2/Documents/Literature/Mendeley/Jain\_1999\_Deterministic job-shop scheduling Past, present and future.pdf:pdf},
issn = {03772217},
journal = {European Journal of Operational Research},
keywords = {computational study,job-shop,review,scheduling theory},
month = mar,
number = {2},
pages = {390--434},
title = {{Deterministic job-shop scheduling: Past, present and future}},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0377221798001131},
volume = {113},
year = {1999}
}
@article{liblinear,
author = {Fan, Rong-en and Wang, Xiang-rui and Lin, Chih-jen},
file = {:home/hei2/Documents/Literature/Mendeley/Fan, Wang, Lin\_2008\_LIBLINEAR A Library for Large Linear Classification.pdf:pdf},
journal = {Corpus},
keywords = {large-scale linear classification,logistic regression,machine learning,open source,support vector machines},
pages = {1871--1874},
title = {{LIBLINEAR : A Library for Large Linear Classification}},
volume = {9},
year = {2008},
note={Software available at \url{http://www.csie.ntu.edu.tw/\hbox{~}cjlin/liblinear}}
}
@inbook{JansenKlausAndZhang2007,
author = {{Jansen, Klaus And Zhang}, Hu},
booktitle = {Handbook of Approximation Algorithms and Metaheuristics},
editor = {Gonzalez, Teofilo F.},
file = {:home/hei2/Documents/Literature/Mendeley/Jansen, Klaus And Zhang\_2007\_Scheduling Malleable Tasks.pdf:pdf},
isbn = {978-1-58488-550-4},
publisher = {Chapman and Hall/CRC},
title = {{Scheduling Malleable Tasks}},
year = {2007}
}
@article{Jayamohan2004,
author = {Jayamohan, M},
doi = {10.1016/S0377-2217(03)00204-2},
file = {:home/hei2/Documents/Literature/Mendeley/Jayamohan\_2004\_Development and analysis of cost-based dispatching rules for job shop scheduling.pdf:pdf},
issn = {03772217},
journal = {European Journal of Operational Research},
keywords = {dispatching rules,job shop,scheduling,weighted flowtime,weighted tardiness},
month = sep,
number = {2},
pages = {307--321},
title = {{Development and analysis of cost-based dispatching rules for job shop scheduling}},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0377221703002042},
volume = {157},
year = {2004}
}
@article{Kanet2004,
author = {Kanet, John J. and Li, Xiaoming},
doi = {10.1023/B:JOSH.0000031421.64487.95},
file = {:home/hei2/Documents/Literature/Mendeley/Kanet, Li\_2004\_A Weighted Modified Due Date Rule for Sequencing to Minimize Weighted Tardiness.pdf:pdf},
issn = {1094-6136},
journal = {Journal of Scheduling},
keywords = {priority rules,scheduling,single machine,weighted tardiness},
month = jul,
number = {4},
pages = {261--276},
title = {{A Weighted Modified Due Date Rule for Sequencing to Minimize Weighted Tardiness}},
url = {http://www.springerlink.com/openurl.asp?id=doi:10.1023/B:JOSH.0000031421.64487.95},
volume = {7},
year = {2004}
}
@article{Kurtulus1982a,
annote = {Heuristics:
* MINSLK - minimum slack
* FCFS - first come first served
* SOF - shortest operation first
* LALP - longest activity from the longest project
* SASP - shortest activity from the shortest project
* MOF - maximum operations first
* MAXSLK - maximum slack first
* MINTWK - minimum total work content
* MAXTWK - maximum total work content

        
Measures of goodness
* ARLF - average resource load factor
* AUF - average utilization factor, aka average tightness of the contraints on each required resource},
author = {Kurtulus, I. and Davis, E. W.},
doi = {10.1287/mnsc.28.2.161},
file = {:home/hei2/Documents/Literature/Mendeley/Kurtulus, Davis\_1982\_Multi-Project Scheduling Categorization of Heuristic Rules Performance.pdf:pdf},
issn = {0025-1909},
journal = {Management Science},
month = feb,
number = {2},
pages = {161--172},
title = {{Multi-Project Scheduling: Categorization of Heuristic Rules Performance}},
url = {http://mansci.journal.informs.org/cgi/doi/10.1287/mnsc.28.2.161},
volume = {28},
year = {1982}
}
@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{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{Marecek2010,
annote = {Skoða kafla 45. Scheduling Malleable Tasks (bls. 665-680)

        
Malleable tasks:
1) independent MTs (IMTs)
2) precedence constraints between MTs (PCMTs)

        
n independent or precedent-contrainted MTs
m processors
obj. min makespan

        
Perform transformation for a solution of the knapsack problem.},
author = {Marecek, J.},
doi = {10.1093/comjnl/bxp121},
file = {:home/hei2/Documents/Literature/Mendeley/Marecek\_2010\_Handbook of Approximation Algorithms and Metaheuristics.pdf:pdf},
issn = {0010-4620},
journal = {The Computer Journal},
month = jan,
title = {{Handbook of Approximation Algorithms and Metaheuristics}},
url = {http://comjnl.oxfordjournals.org/cgi/doi/10.1093/comjnl/bxp121},
year = {2010}
}
@article{Olafsson2008,
author = {Olafsson, S and Li, X and Wu, S},
doi = {10.1016/j.ejor.2006.09.023},
file = {:home/hei2/Documents/Literature/Mendeley/Olafsson, Li, Wu\_2008\_Operations research and data mining.pdf:pdf},
issn = {03772217},
journal = {European Journal of Operational Research},
keywords = {classification,clustering,data mining,heuristics,mathematical programming,optimization},
month = jun,
number = {3},
pages = {1429--1448},
title = {{Operations research and data mining}},
url = {http://linkinghub.elsevier.com/retrieve/pii/S037722170600854X},
volume = {187},
year = {2008}
}
@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}
}
@article{Park2000,
annote = {min tardiness

        
scheduling on several identical machines

        
Heuristics:
* EDD - Earliest due dates
* WSPT - weighted shortest processing time
* MSLACK - minimum slack
* S/RPT - slack per remaining processing time
* SPT - shortest processing time
* COVERT - cost overt ime
* ATC - apparent tardiness cost
* FCFS - first come first serve
* LSR - least slack remaining

        

        
Problem characteristics:
* due date tightness, tau = 1-avg(d)/C\_max, where avg(d) are the average of the due dates and C\_max is the makespan. So tau has the range [0,1]. Note C\_max needs to be approximated.},
author = {Park, Y and Kim, S. and Lee, Y.H.},
doi = {10.1016/S0360-8352(00)00038-3},
file = {:home/hei2/Documents/Literature/Mendeley/Park, Kim, Lee\_2000\_Scheduling jobs on parallel machines applying neural network and heuristic rules.pdf:pdf},
issn = {03608352},
journal = {Computers \& Industrial Engineering},
keywords = {82-562-279-2870,ac,bubble,corresponding author,e-mail addresses,fax,heuristic rule,kim,kr,neural network,parallel machines,park,postech,pys,s,scheduling,sequence dependent setup time,sookim,y,yonsei,youngh},
month = jan,
number = {1},
pages = {189--202},
publisher = {Elsevier},
title = {{Scheduling jobs on parallel machines applying neural network and heuristic rules}},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0360835200000383},
volume = {38},
year = {2000}
}
@article{Runarsson1999,
author = {Runarsson, T.P. and Jonsson, M.T.},
file = {::},
journal = {Journal of Intelligent Manufacturing},
number = {2},
pages = {181--186},
publisher = {Springer},
title = {{Genetic production systems for intelligent problem solving}},
url = {http://www.springerlink.com/index/UM6345K504M5V507.pdf},
volume = {10},
year = {1999}
}
@inproceedings{Russell2005,
author = {Russell, Tyrel and Malik, A.M. and Chase, Michael and van Beek, P.},
booktitle = {Proceedings of the 2005 conference of the Centre for Advanced Studies on Collaborative research},
file = {::},
pages = {253},
publisher = {IBM Press},
title = {{Learning basic block scheduling heuristics from optimal data}},
url = {http://portal.acm.org/citation.cfm?id=1105634.1105652},
year = {2005}
}
@article{Russell2009,
author = {Russell, Tyrel and Malik, Abid M. and Chase, Michael and van Beek, Peter},
doi = {10.1109/TKDE.2009.17},
file = {:home/hei2/Documents/Literature/Mendeley/Russell et al.\_2009\_Learning Heuristics for the Superblock Instruction Scheduling Problem.pdf:pdf},
issn = {1041-4347},
journal = {IEEE Transactions on Knowledge and Data Engineering},
month = oct,
number = {10},
pages = {1489--1502},
title = {{Learning Heuristics for the Superblock Instruction Scheduling Problem}},
url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=4752820},
volume = {21},
year = {2009}
}
@article{Sabuncuoglu1998,
author = {Sabuncuoglu, Ihsan and Karabuk, Suleyman},
doi = {10.1080/07408179808966449},
file = {::},
issn = {0740-817X},
journal = {IIE Transactions},
month = feb,
number = {2},
pages = {179--191},
title = {{A beam search-based algorithm and evaluation of scheduling approaches for flexible manufacturing systems}},
url = {http://www.informaworld.com/openurl?genre=article\&doi=10.1080/07408179808966449\&magic=crossref||D404A21C5BB053405B1A640AFFD44AE3},
volume = {30},
year = {1998}
}
@article{Taillard1994,
author = {Taillard, E.},
file = {:home/hei2/Documents/Literature/Mendeley/Taillard\_1994\_Parallel taboo search techniques for the job shop scheduling problem.pdf:pdf},
journal = {ORSA journal on Computing},
pages = {108--108},
publisher = {ORSA BUSINESS OFFICE},
title = {{Parallel taboo search techniques for the job shop scheduling problem}},
url = {http://mistic.heig-vd.ch/taillard/articles.dir/jobshop.pdf},
volume = {6},
year = {1994}
}
@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}
}
@article{Thiagarajan2005,
annote = {Minimising costs due to 
* earliness (finished before due date)
* tardiness (finished after due date)
* holding (time job is idle after production starts) -- flowtime

        
New dispatching rules:
* relative remaining operations (RRO)
* relative remaining process time (RRP)
* importance ratio (IR)

        
Total Work Content Remaining (TWKR)
* tie-break between equally important jobs. 
* tie breaking rules for RRO and RRP
* also known as total processing times of remaining operations on the job

        

        
Rules under investigation:

        4.1 TWKR - total work content of all operations remaining to be done on items of the job

        4.2 SPT - shortest processing time

        4.3 JDD - job due date (based on job arrival and critical path time (sum of processing times))

        4.4 ECT - earliest completion time

        4.5 PT-BY-TIS - modify the SPT rule with time spent in the system 
          
4.6 TWKR-BY-TIS  -  the total work remaining modified by considering the time spent 

        4.7 LBE+LBT - lower bound on the completion timei, and hence computes the lower bounds on the earliness cost and the tardiness cost. 

        4.8 LBE+LBT+LBF - lower bound on the completion time, and hence computes the lowerbounds on the earliness cost, the tardiness cost and the holding cost.

        4.9 FIFO - First in first out

        4.10 COVERT - cost over time

        4.11 CR - critical ratio of a job is calculated as the difference between the job due-date and the current time divided by its total remaining processing time.

        4.12 EXPET - similar in basic form to COVERT rule in the sense that it uses slack and cost information. It also includes early cost information and a look-ahead exponential function. The primary feature of this rule is to recognize approaching tardiness and adjust job priorities accordingly.
          
4.13 ATC - Apparent-tardiness-cost is similar to the COVERT rule with two main differences: the slack is considered to be the local resource-constrained slack which takes into account the waiting times on downstream machines and the decay function is exponential rather than linear.},
author = {Thiagarajan, S and Rajendran, C},
doi = {10.1016/j.cie.2005.06.005},
file = {:home/hei2/Documents/Literature/Mendeley//Thiagarajan, Rajendran\_2005\_Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs.pdf:pdf},
issn = {03608352},
journal = {Computers \& Industrial Engineering},
keywords = {JSP,JSP features},
mendeley-tags = {JSP,JSP features},
number = {4},
pages = {463--503},
title = {{Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs}},
url = {http://linkinghub.elsevier.com/retrieve/pii/S036083520500104X},
volume = {49},
year = {2005}
}
@inproceedings{Zhang1995,
author = {Zhang, Wei and Dietterich, Thomas G.},
booktitle = {Advances in Neural Information Processing Systems},
editor = {Touretzky, D. S. and Mozer, M. C. and Hasselmo, M. E.},
file = {:home/hei2/Documents/Literature/Mendeley/Zhang, Dietterich\_1995\_High-performance Job-Shop Scheduling with a Time-delay TD($\lambda$) Network.pdf:pdf},
keywords = {NIPS},
title = {{High-performance Job-Shop Scheduling with a Time-delay TD($\lambda$) Network}},
year = {1995}
}
@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}
}