# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates. (English) Zbl 1208.90066
Summary: We address the parallel machine total weighted tardiness scheduling problem with release dates. We describe dominance rules and filtering methods for this problem. Most of them are adaptations of dominance rules based on solution methods for the single-machine problem. We show how it is possible to deduce whether or not certain jobs can be processed by a particular machine in a particular context and we describe techniques that use this information to improve the dominance rules. On the basis of these techniques we describe an enumeration procedure and we provide experimental results to determine the effectiveness of the dominance rules.

##### MSC:
 90B35 Scheduling theory, deterministic
Full Text:
##### References:
 [1] Akturk, M. S.; Ozdemir, D.: An exact approach to minimizing total weighted tardiness with release dates, IIE transactions 32, 1091-1101 (2000) [2] Akturk, M. S.; Ozdemir, D.: A new dominance rule to minimize total weighted tardiness with unequal release dates, European journal of operational research 135, 394-412 (2001) · Zbl 1051.90013 · doi:10.1016/S0377-2217(00)00319-2 [3] Azizoglu, M.; Kirca, O.: Tardiness minimization on parallel machines, International journal of production economics 55, 163-168 (1998) [4] Baker, K. R.: Introduction to sequencing and scheduling, (1974) [5] Baptiste, Ph.: Scheduling equal-length jobs on identical parallel machines, Discrete applied mathematics 13, 21-32 (2000) · Zbl 0971.90027 · doi:10.1016/S0166-218X(99)00238-3 [6] Baptiste, Ph.; Carlier, J.; Jouglet, A.: A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates, European journal of operational research 158, No. 3, 595-608 (2004) · Zbl 1056.90054 · doi:10.1016/S0377-2217(03)00378-3 [7] Baptiste, Ph.; Jouglet, A.; Savourey, D.: Lower bounds for parallel machine scheduling problems, International journal of operational research 3, No. 6, 661-682 (2008) · Zbl 1144.90376 · doi:10.1504/IJOR.2008.019731 [8] Brucker, P.: Scheduling algorithms, (1995) · Zbl 0839.90059 [9] Carlier, J.: Ordonnancements à contraintes disjonctives, Rairo 12, 333-351 (1978) · Zbl 0401.90052 [10] Chu, C.: A branch and bound algorithm to minimize total flow time with unequal release dates, Naval research logistics 39, 859-875 (1992) · Zbl 0766.90039 · doi:10.1002/1520-6750(199210)39:6<859::AID-NAV3220390610>3.0.CO;2-W [11] Chu, C.: A branch and bound algorithm to minimize total tardiness with different release dates, Naval research logistics 39, 265-283 (1992) · Zbl 0762.90035 · doi:10.1002/1520-6750(199203)39:2<265::AID-NAV3220390209>3.0.CO;2-L [12] Chu, C.; Portmann, M. -C.: Some new efficients methods to solve the n$\vert 1\vert$ri$\vert \sum$Ti, European journal of operational research 58, 404-413 (1991) [13] Conway, R. W.; Maxwell, W. L.; Miller, L. W.: Theory of scheduling, (1967) · Zbl 1058.90500 [14] Ignall, E.; Schrage, L.: Applications of the branch-and-bound technique to some flow-shop scheduling problems, Operations research 13, 400-412 (1965) [15] Jouglet, A.; Baptiste, Ph.; Carlier, J.: Branch-and-bound algorithms for total weighted tardiness, Handbook of scheduling: algorithms models and performance analysis, vol. 13 13, 1-21 (2004) [16] Jouglet, A.; Savourey, D.; Carlier, J.; Baptiste, Ph.: Dominance-based heuristics for one-machine total cost scheduling problems, European journal of operational research 184, No. 3, 879-899 (2008) · Zbl 1141.90019 · doi:10.1016/j.ejor.2006.11.036 [17] Kohler, W. H.; Steiglitz, K.: Enumerative and iterative computational approaches, Computer and job-shop scheduling theory, vol. 6 6, 229-287 (1976) [18] Lenstra, J.; Kan, A. R.; Brucker, P.: Complexity of machine scheduling problems, Annals of discrete mathematics 1, 343-362 (1977) · Zbl 0353.68067 [19] Liaw, C. -F.; Lin, Y. -K.; Cheng, C. -Y.; Chen, M.: Scheduling unrelated parallel machines to minimize total weighted tardiness, Computers & operations research, 1777-1789 (2003) · Zbl 1047.90021 · doi:10.1016/S0305-0548(02)00105-3 [20] Mitten, L.: Branch-and-bound methods: general formulation and properties, Operations research 18, No. 1, 24-34 (1970) · Zbl 0225.90030 · doi:10.1287/opre.18.1.24 [21] Nessah, R.; Yalaoui, F.; Chu, C.: A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates, Computers & operations research 35, No. 4, 1176-1190 (2008) · Zbl 1180.90133 · doi:10.1016/j.cor.2006.07.010 [22] Savourey D. Ordonnancement sur machines parallèles: minimiser la somme des coûts. PhD thesis, Université de Technologie de Compiègne, France; 2006. [23] Shim, S. -O.; Kim, Y. -D.: Scheduling on parallel identical machines to minimize total tardiness, European journal of operational research, 135-146 (2007) · Zbl 1111.90046 · doi:10.1016/j.ejor.2005.09.038 [24] Walker, R.: An enumerative technique for a class of combinatorial problems, American mathematical society symposia in applied mathematics 10, 91-94 (1960) · Zbl 0096.00603 [25] Yalaoui, F.; Chu, C.: Parallel machine scheduling to minimize total tardiness, International journal of production economics 76, 265-279 (2002) [26] Yalaoui, F.; Chu, C.: New exact method to solve the pm$\vert$ri$\vert \sum$Ci problem, International journal of production economics 100, No. 1, 168-179 (2006)