zbMATH — the first resource for mathematics

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.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
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)
A note on the complexity of the problem of two-agent scheduling on a single machine. (English) Zbl 1126.90027
Summary: We consider a two-agent scheduling problem on a single machine, where the objective is to minimize the total completion time of the first agent with the restriction that the number of tardy jobs of the second agent cannot exceed a given number. It is reported in the literature that the complexity of this problem is still open. We show in this paper that this problem is NP-hard under high multiplicity encoding and can be solved in pseudo-polynomial time under binary encoding. When the first agent’s objective is to minimize the total weighted completion time, we show that the problem is strongly NP-hard even when the number of tardy jobs of the second agent is restricted to be zero.

90B35Scheduling theory, deterministic
68Q17Computational difficulty of problems
Full Text: DOI
[1] Agnetis A, Mirchandani PB, Pacciarelli D, Pacifici A (2004) Scheduling problems with two competing agents. Oper Res 52:229--242 · Zbl 1165.90446 · doi:10.1287/opre.1030.0092
[2] Clifford JJ, Posner ME (2001) Parallel scheduling with high multiplicity. Mathematical Programming, Ser. A, 89:359--383 · Zbl 0978.90044 · doi:10.1007/PL00011403
[3] Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco, CA · Zbl 0411.68039
[4] Hochbaum DS, Shamir R (1991) Strongly polynomial algorithms for the high multiplicity scheduling problem. Oper Res 39:648--653 · Zbl 0736.90043 · doi:10.1287/opre.39.4.648
[5] Lawler EL (1977) A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals Discr Math, 1:331--342 · Zbl 0353.68071 · doi:10.1016/S0167-5060(08)70742-8
[6] Moore JM (1968) An n job, one machine sequencing algorithm for minimizing the number of late jobs. Manag Sci 15:102--109 · Zbl 0164.20002 · doi:10.1287/mnsc.15.1.102
[7] Rinnooy Kan AHG (1976) Machine scheduling problems. Martinus Nijhoff, The Hague