# 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)
Minmax earliness-tardiness costs with unit processing time jobs. (English) Zbl 0983.90022
Summary: The problem addressed in this paper is defined by $M$ parallel identical machines, $N$ jobs with identical (unit) processing time, job-dependent weights, and a common due-date for all jobs. The objective is of a minmax type, i.e. we are interested in minimizing the cost of the worst scheduled job. In the case of a non-restrictive (i.e., sufficiently large) common due-date, the problem is shown to have a solution that is polynomial in the number of jobs. The solution in the case of a restrictive due-date remains polynomial in the number of jobs, but is exponential in the number of machines. We introduce a lower bound on the optimal cost and an efficient heuristic. We show that the worst case relative error of the heuristic is bounded by 2 and that this bound is tight. We also prove that the heuristic is asymptotically optimal under very general assumptions. Finally, we provide an extensive numerical study demonstrating that in most cases the heuristic performs extremely well.

##### MSC:
 90B35 Scheduling theory, deterministic 90C59 Approximation methods and heuristics
Full Text:
##### References:
 [1] Baker, K.; Scudder, G.: Sequencing with earliness and tardiness penalties: A review. Operations research 38, 22-36 (1990) · Zbl 0699.90052 [2] Cheng, T. C. E.; Chen, Z. L.: Parallel-machine scheduling problems with earliness and tardiness penalties. Journal of operational research society 45, 685-695 (1994) · Zbl 0829.90077 [3] De, P.; Ghosh, J. B.; Wells, C. E.: Due-date assignment and early/tardy scheduling on identical parallel machines. Naval research logistics 41, 17-32 (1994) · Zbl 0794.90022 [4] Dyer, M. E.: Linear time algorithms for two- and three-variable linear programs. SIAM journal of computing 13, 31-45 (1984) · Zbl 0532.90063 [5] Emmons, H.: Scheduling to a common due-date on parallel uniform processors. Naval research logistics 34, 803-810 (1987) · Zbl 0648.90043 [6] Federgruen, A.; Mosheiov, G.: Heuristics for multi-machine scheduling problems with earliness and tardiness costs. Management science 42, 1544-1555 (1996) · Zbl 0879.90115 [7] Federgruen, A.; Mosheiov, G.: Heuristics for multi-machine minmax scheduling problems with general earliness and tardiness costs. Naval research logistics 44, 287-299 (1997) · Zbl 0890.90100 [8] Garey, M. R.; Tarjan, R. E.; Wilfong, G. T.: One processor scheduling with symmetric earliness and tardiness penalties. Mathematics of operations research 13, 330-348 (1988) · Zbl 0671.90033 [9] Hall, N.: Single- and multi-processor models for minimizing completion time variance. Naval research logistics 33, 49-54 (1986) · Zbl 0599.90057 [10] Hall, N.; Kubiak, W.; Sethi, S.: Earliness--tardiness scheduling problems, II: Deviation of completion times about a restrictive common due date. Operations research 39, 847-856 (1991) · Zbl 0762.90037 [11] Hall, N.; Posner, M.: Earliness--tardiness scheduling problems, I: Weighted deviation of completion times about a common due date. Operations research 39, 836-846 (1991) · Zbl 0749.90041 [12] Hardy, G. H.; Littlewood, J. E.; Polya, G.: Inequalities. (1967) [13] Hsu, W. L.: Approximation algorithms for the assembly line crew scheduling problem. Mathematics of operations research 9, 376-383 (1984) · Zbl 0555.90054 [14] Kubiak, W.; Lou, S.; Sethi, S.: Equivalence of mean flow time problems and mean absolute deviation problems. Operations research letters 9, 371-374 (1990) · Zbl 0825.90553 [15] Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D., 1993. Sequencing and scheduling: Algorithms and complexity. In: Graves, S.S., Rinnooy Kan, A.H.G., Zipkin, P. (Eds.), Handbooks in Operations Research and Management Science, vol. 4. North-Holland, New York, pp. 445--522 [16] Li, C. -L.; Chen, Z. L.; Cheng, T. C. E.: A note on one processor scheduling with asymmetry earliness and tardiness penalties. Operations research letters 13, 45-48 (1993) · Zbl 0773.90037 [17] Li, C. -L.; Cheng, T. C. E.: The parallel machine MIN--MAX weighted absolute lateness scheduling problem. Naval research logistics 41, 33-46 (1994) · Zbl 0808.90082 [18] Mosheiov, G., 1991. Scheduling problems with general earliness and tardiness cost structure: A just in time approach. Ph.D. Dissertation, Columbia University, New York [19] Sundararaghavan, P.; Ahmed, M.: Minimizing the sum of absolute lateness in single-machine and multi-machine scheduling. Naval research logistics quarterly 31, 325-333 (1984) · Zbl 0544.90052