%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/
%% Created for Christoph Durr at 2019-02-15 16:38:47 +0100
%% Saved with string encoding Unicode (UTF-8)
@article{Woeginger:97:A-polynomial-time,
Author = {Gerhard J. Woeginger},
Date-Added = {2019-02-15 16:36:37 +0100},
Date-Modified = {2019-02-15 16:38:46 +0100},
Doi = {https://doi.org/10.1016/S0167-6377(96)00055-7},
Issn = {0167-6377},
Journal = {Operations Research Letters},
Keywords = {Scheduling, Approximation algorithm, Worst-case analysis, Approximation scheme},
Number = {4},
Pages = {149 - 154},
Title = {A polynomial-time approximation scheme for maximizing the minimum machine completion time},
Url = {http://www.sciencedirect.com/science/article/pii/S0167637796000557},
Volume = {20},
Year = {1997},
Abstract = {We consider the problem of assigning a set of n jobs to a system of m identical parallel machines so as to maximize the earliest machine completion time (without using idle times). This problem has applications in the sequencing of maintenance actions for modular gas turbine aircraft engines. Up to now, only approximation algorithms were known whose worst case ratio was bounded strictly away from one. In this note, we derive the first polynomial-time approximation scheme for this problem. The time complexity of our algorithms is O(cɛnlogm), where cɛ is a constant that depends on the desired precision ɛ.},
Annote = {$P||C_{\min}$ has a PTAS running in time $O(c_\epsilon n \log m)$ where $c_\epsilon$ is a constant depending on the desired approximation ratio $1+\epsilon$ },
Bdsk-Url-1 = {http://www.sciencedirect.com/science/article/pii/S0167637796000557},
Bdsk-Url-2 = {https://doi.org/10.1016/S0167-6377(96)00055-7}}
@article{WilliamsonHall:97:Short-shop,
Author = {Williamson, DP and Hall, LA and Hoogeveen, JA and Hurkens, CAJ and Lenstra, Jan Karel and Sevast'Janov, SV and Shmoys, DB},
Date-Added = {2016-02-22 10:07:00 +0000},
Date-Modified = {2016-02-22 10:08:04 +0000},
Journal = {Operations Research},
Number = {2},
Pages = {288--294},
Publisher = {INFORMS},
Title = {Short shop schedules},
Volume = {45},
Year = {1997},
Annote = {$O||C_{\max}$ has polynomial time approximation ratio $\geq 5/4$\\
$F||C_{\max}$ has polynomial time approximation ratio $\geq 5/4$.
}}
@article{HoogeveenLenstra:94:Three-four,
Author = {Hoogeveen, JA and Lenstra, Jan Karel and Veltman, Bart},
Date-Added = {2016-02-22 10:00:04 +0000},
Date-Modified = {2016-02-22 10:00:12 +0000},
Journal = {Operations Research Letters},
Number = {3},
Pages = {129--137},
Publisher = {Elsevier},
Title = {Three, four, five, six, or the complexity of scheduling with communication delays},
Volume = {16},
Year = {1994},
Annote = {$P|prec;l=1;p_j=1|C_{\max}$ polynomial time approximation ratio is $\geq 5/4$.}}
@article{LenstraShmoys:90:Approximation-algorithms,
Author = {Lenstra, Jan Karel and Shmoys, David B and Tardos, {\'E}va},
Date-Added = {2016-02-22 07:50:42 +0000},
Date-Modified = {2016-02-22 07:50:47 +0000},
Journal = {Mathematical programming},
Number = {1-3},
Pages = {259--271},
Publisher = {Springer},
Title = {Approximation algorithms for scheduling unrelated parallel machines},
Volume = {46},
Year = {1990},
Annote = {$R||C_{\max}$ polynomial time approximation ratio $\geq 3/2$}}
@article{HoogeveenSchuurman:01:Non-approximability-results,
Author = {Hoogeveen, Han and Schuurman, Petra and Woeginger, Gerhard J},
Date-Added = {2016-02-22 07:36:04 +0000},
Date-Modified = {2016-02-22 10:10:09 +0000},
Journal = {INFORMS Journal on Computing},
Number = {2},
Pages = {157--168},
Publisher = {INFORMS},
Title = {Non-approximability results for scheduling problems with minsum criteria},
Volume = {13},
Year = {2001},
Annote = {$R|r_j|\sum C_j$ is APX-hard\\
$R||\sum w_jC_j$ is APX-hard\\
$F||\sum C_j$ is APX-hard\\
$O||\sum C_j$ is APX-hard\\
$P|prec;p_j=1|\sum C_j$ is APX-hard\\
$P|prec;l=1;p_j=1|\sum C_j$ is APX-hard.}}
@incollection{Skutella:06:List-scheduling,
Author = {Skutella, Martin},
Booktitle = {Efficient Approximation and Online Algorithms},
Date-Added = {2014-04-28 14:08:16 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Pages = {250--291},
Publisher = {Springer},
Title = {List scheduling in order of $\alpha$-points on a single machine},
Year = {2006},
Annote = {$1|r_j|\sum C_j$ randomized approximation ratio using $\alpha$-points $\leq 1.5820$\\
$1|r_j|\sum w_jC_j$ randomized approximation ratio using $\alpha$-points $\leq 1.6853$\\
$1|r_j;pmtn|\sum C_j$ randomized approximation ratio using $\alpha$-points $\leq 4/3$\\
$1|r_j;prec;pmtn|\sum w_jC_j$ randomized approximation ratio using $\alpha$-points $\leq 2+\epsilon$\\
$1|r_j;prec|\sum w_jC_j$ randomized approximation ratio using $\alpha$-points $\leq e+\epsilon$\\
},
Bdsk-File-1 = {YnBsaXN0MDDSAQIDBFxyZWxhdGl2ZVBhdGhZYWxpYXNEYXRhXxA7Li4vLi4vLi4vWHRvZk1hdGhpZXUvYmlibGlvL1NrdXRlbGxhLTA2LUxpc3Qtc2NoZWR1bGluZy5wZGZPEQHmAAAAAAHmAAIAAAtEaXNxdWUgRJ9ycgAAAAAAAAAAAAAAAAAAAADT/nuHSCsAAAAhUlMfU2t1dGVsbGEtMDYtTGlzdC1zY2hlZHVsaW5nLnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACHpsc+ELbQAAAAAAAAAAAADAAMAAAkgAAAAAAAAAAAAAAAAAAAABmJpYmxpbwAQAAgAANP+X2cAAAARAAgAAM+EEZQAAAABABQAIVJTACFR2wAhUUoACfBCAAZNIwACAFZEaXNxdWUgRJ9ycjpVc2VyczoAZHVycjoARHJvcGJveDoAWHRvZk1hdGhpZXU6AGJpYmxpbzoAU2t1dGVsbGEtMDYtTGlzdC1zY2hlZHVsaW5nLnBkZgAOAEAAHwBTAGsAdQB0AGUAbABsAGEALQAwADYALQBMAGkAcwB0AC0AcwBjAGgAZQBkAHUAbABpAG4AZwAuAHAAZABmAA8AGgAMAEQAaQBzAHEAdQBlACAARAB1AwgAcgByABIARVVzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vU2t1dGVsbGEtMDYtTGlzdC1zY2hlZHVsaW5nLnBkZgAAEwABLwAAFQACAAv//wAAAAgADQAaACQAYgAAAAAAAAIBAAAAAAAAAAUAAAAAAAAAAAAAAAAAAAJM}}
@article{SavelsberghUma:05:An-experimental-study,
Author = {Savelsbergh, Martin WP and Uma, RN and Wein, Joel},
Date-Added = {2014-04-28 14:04:48 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {INFORMS Journal on Computing},
Number = {1},
Pages = {123--136},
Publisher = {INFORMS},
Title = {An experimental study of LP-based approximation algorithms for scheduling problems},
Volume = {17},
Year = {2005},
Annote = {$1|r_j|\sum w_jC_j$ LP-based approximation algorithms are experimentally compared with combinatorial approximation algorithms
}}
@article{SchulzSkutella:02:The-power-of-alpha-points,
Author = {Schulz, Andreas S and Skutella, Martin},
Date-Added = {2014-04-28 13:14:41 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {Journal of Scheduling},
Number = {2},
Pages = {121--133},
Publisher = {Wiley Online Library},
Title = {The power of $\alpha$-points in preemptive single machine scheduling},
Volume = {5},
Year = {2002},
Annote = {$1|r_j;pmtn|\sum w_jC_j$ deterministic approximation ratio $\leq 4/3$ based on $\alpha$-points\\
$1|r_j;pmtn|\sum w_jC_j$ Dyer and Wolsey's time indexed linear programming relaxation has integrality gap $\geq 8/7$\\
},
Bdsk-File-1 = {YnBsaXN0MDDSAQIDBFxyZWxhdGl2ZVBhdGhZYWxpYXNEYXRhXxBLLi4vLi4vLi4vWHRvZk1hdGhpZXUvYmlibGlvL1NjaHVselNrdXRlbGxhLTAyLVRoZS1wb3dlci1vZi1hbHBoYS1wb2ludHMucGRmTxECFgAAAAACFgACAAALRGlzcXVlIESfcnIAAAAAAAAAAAAAAAAAAAAA0/57h0grAAAAIVJTH1NjaHVselNrdXRlbGxhLTAyLVRoIzIyOTkxQy5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAimRzPhCjmAAAAAAAAAAAAAwADAAAJIAAAAAAAAAAAAAAAAAAAAAZiaWJsaW8AEAAIAADT/l9nAAAAEQAIAADPhAzGAAAAAQAUACFSUwAhUdsAIVFKAAnwQgAGTSMAAgBWRGlzcXVlIESfcnI6VXNlcnM6AGR1cnI6AERyb3Bib3g6AFh0b2ZNYXRoaWV1OgBiaWJsaW86AFNjaHVselNrdXRlbGxhLTAyLVRoIzIyOTkxQy5wZGYADgBgAC8AUwBjAGgAdQBsAHoAUwBrAHUAdABlAGwAbABhAC0AMAAyAC0AVABoAGUALQBwAG8AdwBlAHIALQBvAGYALQBhAGwAcABoAGEALQBwAG8AaQBuAHQAcwAuAHAAZABmAA8AGgAMAEQAaQBzAHEAdQBlACAARAB1AwgAcgByABIAVVVzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vU2NodWx6U2t1dGVsbGEtMDItVGhlLXBvd2VyLW9mLWFscGhhLXBvaW50cy5wZGYAABMAAS8AABUAAgAL//8AAAAIAA0AGgAkAHIAAAAAAAACAQAAAAAAAAAFAAAAAAAAAAAAAAAAAAACjA==}}
@article{ChekuriMotwani:99:Precedence-constrained,
Author = {Chekuri, Chandra and Motwani, Rajeev},
Date-Added = {2014-04-28 13:10:48 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {Discrete Applied Mathematics},
Number = {1},
Pages = {29--38},
Publisher = {Elsevier},
Title = {Precedence constrained scheduling to minimize sum of weighted completion times on a single machine},
Volume = {98},
Year = {1999},
Annote = {$1|prec|\sum w_jC_j$ deterministic approximation ratio $\leq 2$
},
Bdsk-File-1 = {YnBsaXN0MDDSAQIDBFxyZWxhdGl2ZVBhdGhZYWxpYXNEYXRhXxBILi4vLi4vLi4vWHRvZk1hdGhpZXUvYmlibGlvL0NoZWt1cmlNb3R3YW5pLTk5LVByZWNlZGVuY2UtY29uc3RyYWluZWQucGRmTxECDAAAAAACDAACAAALRGlzcXVlIESfcnIAAAAAAAAAAAAAAAAAAAAA0/57h0grAAAAIVJTH0NoZWt1cmlNb3R3YW5pLTk5LVByIzIyOEVBNi5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAijqbPhCAjAAAAAAAAAAAAAwADAAAJIAAAAAAAAAAAAAAAAAAAAAZiaWJsaW8AEAAIAADT/l9nAAAAEQAIAADPhAQDAAAAAQAUACFSUwAhUdsAIVFKAAnwQgAGTSMAAgBWRGlzcXVlIESfcnI6VXNlcnM6AGR1cnI6AERyb3Bib3g6AFh0b2ZNYXRoaWV1OgBiaWJsaW86AENoZWt1cmlNb3R3YW5pLTk5LVByIzIyOEVBNi5wZGYADgBaACwAQwBoAGUAawB1AHIAaQBNAG8AdAB3AGEAbgBpAC0AOQA5AC0AUAByAGUAYwBlAGQAZQBuAGMAZQAtAGMAbwBuAHMAdAByAGEAaQBuAGUAZAAuAHAAZABmAA8AGgAMAEQAaQBzAHEAdQBlACAARAB1AwgAcgByABIAUlVzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vQ2hla3VyaU1vdHdhbmktOTktUHJlY2VkZW5jZS1jb25zdHJhaW5lZC5wZGYAEwABLwAAFQACAAv//wAAAAgADQAaACQAbwAAAAAAAAIBAAAAAAAAAAUAAAAAAAAAAAAAAAAAAAJ/}}
@inproceedings{AfratiBampis:99:Approximation-schemes,
Author = {Afrati, Foto and Bampis, Evripidis and Chekuri, Chandra and Karger, David and Kenyon, Claire and Khanna, Sanjeev and Milis, Ioannis and Queyranne, Maurice and Skutella, Martin and Stein, Clifford and others},
Booktitle = {Foundations of Computer Science, 1999. 40th Annual Symposium on},
Date-Added = {2014-04-28 12:35:04 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Organization = {IEEE},
Pages = {32--43},
Title = {Approximation schemes for minimizing average weighted completion time with release dates},
Year = {1999},
Annote = {$P|r_j|\sum w_jC_j$ has a PTAS\\
$P|r_j;pmtn|\sum w_jC_j$ has a PTAS\\
$Rm|r_j|\sum w_jC_j$ has a PTAS\\
$Rm|r_j;pmtn|\sum w_jC_j$ has a PTAS\\
},
Bdsk-File-1 = {YnBsaXN0MDDSAQIDBFxyZWxhdGl2ZVBhdGhZYWxpYXNEYXRhXxBFLi4vLi4vLi4vWHRvZk1hdGhpZXUvYmlibGlvL0FmcmF0aUJhbXBpcy05OS1BcHByb3hpbWF0aW9uLXNjaGVtZXMucGRmTxECBAAAAAACBAACAAALRGlzcXVlIESfcnIAAAAAAAAAAAAAAAAAAAAA0/57h0grAAAAIVJTH0FmcmF0aUJhbXBpcy05OS1BcHByIzIyODdEMC5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAih9DPhBerAAAAAAAAAAAAAwADAAAJIAAAAAAAAAAAAAAAAAAAAAZiaWJsaW8AEAAIAADT/l9nAAAAEQAIAADPg/uLAAAAAQAUACFSUwAhUdsAIVFKAAnwQgAGTSMAAgBWRGlzcXVlIESfcnI6VXNlcnM6AGR1cnI6AERyb3Bib3g6AFh0b2ZNYXRoaWV1OgBiaWJsaW86AEFmcmF0aUJhbXBpcy05OS1BcHByIzIyODdEMC5wZGYADgBUACkAQQBmAHIAYQB0AGkAQgBhAG0AcABpAHMALQA5ADkALQBBAHAAcAByAG8AeABpAG0AYQB0AGkAbwBuAC0AcwBjAGgAZQBtAGUAcwAuAHAAZABmAA8AGgAMAEQAaQBzAHEAdQBlACAARAB1AwgAcgByABIAT1VzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vQWZyYXRpQmFtcGlzLTk5LUFwcHJveGltYXRpb24tc2NoZW1lcy5wZGYAABMAAS8AABUAAgAL//8AAAAIAA0AGgAkAGwAAAAAAAACAQAAAAAAAAAFAAAAAAAAAAAAAAAAAAACdA==}}
@inproceedings{SchulzSkutella:97:Scheduling-LPs-bear,
Author = {Schulz, Andreas S and Skutella, Martin},
Booktitle = {Algorithms---ESA'97},
Date-Added = {2014-04-28 12:13:58 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Organization = {Springer},
Pages = {416--429},
Title = {Scheduling-LPs bear probabilities randomized approximations for min-sum criteria},
Year = {1997},
Annote = {$R|r_j|\sum w_jC_j$ randomized approximation ratio $\leq 2+\epsilon$\\
$P|r_j|\sum w_jC_j$ randomized approximation ratio $\leq 2$\\
$1|r_j|\sum w_jC_j$ randomized approximation ratio $\leq 1.6853$ in time $O(n\log n)$\\
$1|r_j;pmtn|\sum w_jC_j$ randomized approximation ratio $\leq 4/3$
},
Bdsk-File-1 = {YnBsaXN0MDDSAQIDBFxyZWxhdGl2ZVBhdGhZYWxpYXNEYXRhXxBFLi4vLi4vLi4vWHRvZk1hdGhpZXUvYmlibGlvL1NjaHVselNrdXRlbGxhLTk3LVNjaGVkdWxpbmctTFBzLWJlYXIucGRmTxECBAAAAAACBAACAAALRGlzcXVlIESfcnIAAAAAAAAAAAAAAAAAAAAA0/57h0grAAAAIVJTH1NjaHVselNrdXRlbGxhLTk3LVNjIzIyODQ2Qy5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAihGzPhBK6AAAAAAAAAAAAAwADAAAJIAAAAAAAAAAAAAAAAAAAAAZiaWJsaW8AEAAIAADT/l9nAAAAEQAIAADPg/aaAAAAAQAUACFSUwAhUdsAIVFKAAnwQgAGTSMAAgBWRGlzcXVlIESfcnI6VXNlcnM6AGR1cnI6AERyb3Bib3g6AFh0b2ZNYXRoaWV1OgBiaWJsaW86AFNjaHVselNrdXRlbGxhLTk3LVNjIzIyODQ2Qy5wZGYADgBUACkAUwBjAGgAdQBsAHoAUwBrAHUAdABlAGwAbABhAC0AOQA3AC0AUwBjAGgAZQBkAHUAbABpAG4AZwAtAEwAUABzAC0AYgBlAGEAcgAuAHAAZABmAA8AGgAMAEQAaQBzAHEAdQBlACAARAB1AwgAcgByABIAT1VzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vU2NodWx6U2t1dGVsbGEtOTctU2NoZWR1bGluZy1MUHMtYmVhci5wZGYAABMAAS8AABUAAgAL//8AAAAIAA0AGgAkAGwAAAAAAAACAQAAAAAAAAAFAAAAAAAAAAAAAAAAAAACdA==}}
@inproceedings{Goemans:97:Improved-approximation,
Author = {Goemans, Michel X},
Booktitle = {Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms},
Date-Added = {2014-04-28 12:07:46 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Organization = {Society for Industrial and Applied Mathematics},
Pages = {591--598},
Title = {Improved approximation algorthims for scheduling with release dates},
Year = {1997},
Annote = {$1|r_j|\sum w_jC_j$ deterministic approximation ratio $\leq 2$ in time $O(n^2)$
},
Bdsk-File-1 = {YnBsaXN0MDDSAQIDBFxyZWxhdGl2ZVBhdGhZYWxpYXNEYXRhXxBBLi4vLi4vLi4vWHRvZk1hdGhpZXUvYmlibGlvL0dvZW1hbnMtOTctSW1wcm92ZWQtYXBwcm94aW1hdGlvbi5wZGZPEQH4AAAAAAH4AAIAAAtEaXNxdWUgRJ9ycgAAAAAAAAAAAAAAAAAAAADT/nuHSCsAAAAhUlMfR29lbWFucy05Ny1JbXByb3ZlZC0jMjIwMTZELnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACIBbc+EEZEAAAAAAAAAAAADAAMAAAkgAAAAAAAAAAAAAAAAAAAABmJpYmxpbwAQAAgAANP+X2cAAAARAAgAAM+D9XEAAAABABQAIVJTACFR2wAhUUoACfBCAAZNIwACAFZEaXNxdWUgRJ9ycjpVc2VyczoAZHVycjoARHJvcGJveDoAWHRvZk1hdGhpZXU6AGJpYmxpbzoAR29lbWFucy05Ny1JbXByb3ZlZC0jMjIwMTZELnBkZgAOAEwAJQBHAG8AZQBtAGEAbgBzAC0AOQA3AC0ASQBtAHAAcgBvAHYAZQBkAC0AYQBwAHAAcgBvAHgAaQBtAGEAdABpAG8AbgAuAHAAZABmAA8AGgAMAEQAaQBzAHEAdQBlACAARAB1AwgAcgByABIAS1VzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vR29lbWFucy05Ny1JbXByb3ZlZC1hcHByb3hpbWF0aW9uLnBkZgAAEwABLwAAFQACAAv//wAAAAgADQAaACQAaAAAAAAAAAIBAAAAAAAAAAUAAAAAAAAAAAAAAAAAAAJk}}
@inproceedings{HoogeveenVestjens:96:Optimal-On-Line,
Author = {Han Hoogeveen and Arjen P. A. Vestjens},
Bibsource = {DBLP, http://dblp.uni-trier.de},
Booktitle = {IPCO},
Date-Added = {2014-04-28 11:58:59 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Editor = {William H. Cunningham and S. Thomas McCormick and Maurice Queyranne},
Ee = {http://dx.doi.org/10.1007/3-540-61310-2_30},
Isbn = {3-540-61310-2},
Pages = {404-414},
Publisher = {Springer},
Series = {Lecture Notes in Computer Science},
Title = {Optimal On-Line Algorithms for Single-Machine Scheduling},
Volume = {1084},
Year = {1996},
Annote = {$1|r_j|\sum w_jC_j$ deterministic approximation ratio $\leq 2$\\
$1|online-r_j|\sum w_jC_j$ deterministic approximation ratio $\leq 2$\\
$1|online-r_j|\sum w_jC_j$ deterministic approximation ratio $\geq 2$\\
},
Bdsk-File-1 = {YnBsaXN0MDDSAQIDBFxyZWxhdGl2ZVBhdGhZYWxpYXNEYXRhXxBELi4vLi4vLi4vWHRvZk1hdGhpZXUvYmlibGlvL0hvb2dldmVlblZlc3RqZW5zLTk2LU9wdGltYWwtT24tTGluZS5wZGZPEQIAAAAAAAIAAAIAAAtEaXNxdWUgRJ9ycgAAAAAAAAAAAAAAAAAAAADT/nuHSCsAAAAhUlMfSG9vZ2V2ZWVuVmVzdGplbnMtOTYjMjIwQkM1LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACILxc+EFjgAAAAAAAAAAAADAAMAAAkgAAAAAAAAAAAAAAAAAAAABmJpYmxpbwAQAAgAANP+X2cAAAARAAgAAM+D+hgAAAABABQAIVJTACFR2wAhUUoACfBCAAZNIwACAFZEaXNxdWUgRJ9ycjpVc2VyczoAZHVycjoARHJvcGJveDoAWHRvZk1hdGhpZXU6AGJpYmxpbzoASG9vZ2V2ZWVuVmVzdGplbnMtOTYjMjIwQkM1LnBkZgAOAFIAKABIAG8AbwBnAGUAdgBlAGUAbgBWAGUAcwB0AGoAZQBuAHMALQA5ADYALQBPAHAAdABpAG0AYQBsAC0ATwBuAC0ATABpAG4AZQAuAHAAZABmAA8AGgAMAEQAaQBzAHEAdQBlACAARAB1AwgAcgByABIATlVzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vSG9vZ2V2ZWVuVmVzdGplbnMtOTYtT3B0aW1hbC1Pbi1MaW5lLnBkZgATAAEvAAAVAAIAC///AAAACAANABoAJABrAAAAAAAAAgEAAAAAAAAABQAAAAAAAAAAAAAAAAAAAm8=}}
@article{ChekuriMotwani:01:Approximation-techniques,
Author = {Chekuri, Chandra and Motwani, Rajeev and Natarajan, Balas and Stein, Clifford},
Date-Added = {2014-04-28 11:34:04 +0000},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {SIAM Journal on Computing},
Number = {1},
Pages = {146--166},
Publisher = {SIAM},
Title = {Approximation techniques for average completion time scheduling},
Volume = {31},
Year = {2001},
Annote = {$1|r_j|\sum w_jC_j$ randomized approximation ratio $\leq e/(e-1) \approx 1.58$ by algorithm BEST-$\alpha$\\
$1|r_j|\sum w_jC_j$ randomized (oblivious model) competitive ratio $\leq e/(e-1) \approx 1.58$ by algorithm BEST-$\alpha$\\
},
Bdsk-File-1 = {YnBsaXN0MDDSAQIDBFxyZWxhdGl2ZVBhdGhZYWxpYXNEYXRhXxBKLi4vLi4vLi4vWHRvZk1hdGhpZXUvYmlibGlvL0NoZWt1cmlNb3R3YW5pLTAxLUFwcHJveGltYXRpb24tdGVjaG5pcXVlcy5wZGZPEQISAAAAAAISAAIAAAtEaXNxdWUgRJ9ycgAAAAAAAAAAAAAAAAAAAADT/nuHSCsAAAAhUlMfQ2hla3VyaU1vdHdhbmktMDEtQXAjMjI5NjI2LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACKWJs+ECzoAAAAAAAAAAAADAAMAAAkgAAAAAAAAAAAAAAAAAAAABmJpYmxpbwAQAAgAANP+X2cAAAARAAgAAM+D7xoAAAABABQAIVJTACFR2wAhUUoACfBCAAZNIwACAFZEaXNxdWUgRJ9ycjpVc2VyczoAZHVycjoARHJvcGJveDoAWHRvZk1hdGhpZXU6AGJpYmxpbzoAQ2hla3VyaU1vdHdhbmktMDEtQXAjMjI5NjI2LnBkZgAOAF4ALgBDAGgAZQBrAHUAcgBpAE0AbwB0AHcAYQBuAGkALQAwADEALQBBAHAAcAByAG8AeABpAG0AYQB0AGkAbwBuAC0AdABlAGMAaABuAGkAcQB1AGUAcwAuAHAAZABmAA8AGgAMAEQAaQBzAHEAdQBlACAARAB1AwgAcgByABIAVFVzZXJzL2R1cnIvRHJvcGJveC9YdG9mTWF0aGlldS9iaWJsaW8vQ2hla3VyaU1vdHdhbmktMDEtQXBwcm94aW1hdGlvbi10ZWNobmlxdWVzLnBkZgATAAEvAAAVAAIAC///AAAACAANABoAJABxAAAAAAAAAgEAAAAAAAAABQAAAAAAAAAAAAAAAAAAAoc=}}
@article{KellererStrusevich:06:A-fully-polynomial,
Author = {Kellerer, H. and Strusevich, V.A.},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {Theoretical computer science},
Number = {1},
Pages = {230--238},
Publisher = {Elsevier},
Title = {A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date},
Volume = {369},
Year = {2006},
Annote = {$1 | d_j=d | \sum w_jT_j$ has an FPTAS}}
@article{Jinjiang:92:The-NP-hardness-of-the-single,
Author = {JUAN Jinjiang},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {System Science and Mathematical Sciences},
Number = {4},
Pages = {328--333},
Title = {The {NP}-hardness of the single machine common due date weighted tardiness problem},
Volume = {5},
Year = {1992},
Annote = {$1 | d_j=d | \sum w_jT_j$ is $\NP$-hard}}
@article{LawlerMoore:69:A-functional-equation,
Author = {Lawler, E.L. and Moore, J.M.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Management Sci.},
Number = {1},
Pages = {77-84},
Publisher = {INFORMS},
Title = {A functional equation and its application to resource allocation and sequencing problems},
Volume = 16,
Year = 1969,
Annote = {$1||\sum w_jU_j$ is in $P_{pseudo}$,\\
$1 | d_j=d | \sum w_jT_j$ is in $P_{pseudo}$ with time complexity $O(n^2d)$\\
$1||\sum w_jU_j$ is NP-hard.}}
@inproceedings{ManaaHanen:10:On-scheduling-with,
Author = {Manaa, A. and Hanen, C.},
Booktitle = {Proceedings of the {E}uropean {C}onference of {O}perational, {R}esearch (EURO, {L}isbon)},
Date-Modified = {2015-12-21 23:13:08 +0000},
Title = {On scheduling with negative time lags},
Year = {2010},
Annote = {$1|p_j=1;prec;l_{ij}\leq0|L_{\max}$ is $\NP$-hard by reduction from 3-SAT.}}
@article{BaptisteBrucker:15:The-Complexity-of-Mean,
Author = {Philippe Baptiste and Peter Brucker and Marek Chrobak and Christoph D{\"u}rr and Svetlana A. Kravchenko and Francis Sourd},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {Journal of Scheduling},
Title = {The Complexity of Mean Flow Time Scheduling Problems with Release Times},
Year = {to appear},
Annote = {$P | r_j;pmtn;p_j=p | \sum C_j$ is solvable by a linear program of size $O(nm)$}}
@article{Bellenguez.ea:15:A-Note-on-NP-Hardness,
Author = {Odile Bellenguez-Morineau and Marek Chrobak and Christoph D\"urr and Damien Prot},
Journaltitle = {Journal of Scheduling},
Number = {3},
Pages = {299--304},
Title = {A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines},
Volume = {18},
Year = {2015},
Annote = {$P | r_j;pmtn| \sum C_j$ is strongly NP-hard}}
@inproceedings{DurrHurand:06:Finding-total,
Author = {Christoph D{\"u}rr and Mathilde Hurand},
Booktitle = {Proc. of the 14th Annual European Symposium on Algorithms (ESA)},
Date-Modified = {2015-12-21 23:13:08 +0000},
Title = {Finding total unimodularity in optimization problems solved by linear programs},
Year = {2006},
Annote = {$P|r_j;p_j=1;size_j\in\{1,m\}|L_{\max}$ the decision version is solvable in $O(n^3)$.}}
@article{ChrobakDurr:06:A-Note-on-Scheduling,
Author = {Marek Chrobak and Christoph D{{\"u}}rr and Wojciech Jawor and Lukasz Kowalik and Maciej Kurowski},
Date-Modified = {2015-12-21 23:13:08 +0000},
Journal = {Journal of Scheduling},
Number = {1},
Pages = {71--73},
Title = {A Note on Scheduling Equal-Length Jobs to Maximize Throughput},
Volume = {9},
Year = {2006},
Annote = {$1|r_j;p_j=p|\sum U_j$ is solvable in $O(n^5)$.}}
@article{BaptisteChrobak:04:Preemptive-scheduling,
Author = {Baptiste, Philippe and Chrobak, Marek and D{\"u}rr, Christoph and Jawor, Wojciech and Vakhania, Nodari},
Date-Modified = {2015-12-21 23:13:08 +0000},
Fjournal = {Operations Research Letters},
Number = {3},
Pages = {258--264},
Title = {Preemptive scheduling of equal-length jobs to maximize weighted throughput},
Volume = {32},
Year = {2004},
Annote = {$1|r_j;pmtn;p_j=p|\sum w_jU_j$ is solvable in $O(n^4)$.}}
@article{BaptisteSchieber:03:A-note-on-scheduling,
Author = {Baptiste, P. and Schieber, B.},
Date-Modified = {2015-12-21 23:13:08 +0000},
Fjournal = {Journal of Scheduling},
Journal = {J. Sched.},
Number = 4,
Pages = {395-404},
Title = {A note on scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness},
Volume = 6,
Year = 2003,
Annote = {$P2|r_j;p_j=1;size_j|L_{\max}$ is in $P$\\
$P|r_j;p_j=1;size_j\in\{1,m\}|L_{\max}$ can be decided with an LP of $O(n^2)$ var.}}
@unpublished{ProtBellenguez-Morineau:12:,
Author = {D. Prot and O. Bellenguez-Morineau and C. Lahlou},
Date-Modified = {2015-12-21 23:13:08 +0000},
Note = {personal communcation},
Year = {2012},
Annote = {$P|r_j;pmtn|\sum C_j$ NP-hardness proof of [BBCDKS] has a bug}}