but something inspired the group to decide that a book containing a list of all scheduling
problems and whether they had been solved would make a nice gift for their friend and
colleague Alexander Rinnooy Kan, who was about to defend his thesis. (This story appears
in Lawler, “Old Stories,” and Lenstra, “The Mystical Power of Twoness.”) Rinnooy Kan
would go on to make important contributions not just to academia but also to the Dutch
economy, sitting on the board of directors at ING and being named by the newspaper De
Volkskrant as the most influential person in the Netherlands—three years in a row. See
“Rinnooy Kan weer invloedrijkste Nederlander,” De Volkskrant, December 4, 2009,
http://nos.nl/artikel/112743-rinnooy-kan-weer-invloedrijkste-nederlander.html.
Lageweg wrote a computer program that generated the list, enumerating some 4,536
different permutations of the scheduling problem: every possible combination of metrics
(maximum lateness, number of late jobs, sum of completion times, etc.) and constraints
(weights, precedence, start times, and so on) that they could think of. Over a series of
enthralling days, the group “had the pleasure of knocking off one obscure problem type
after another in rapid succession.”
Their organizational schema for describing the zoo of scheduling problems was a
language “laced with shorthand,” which they called “Schedulese” (Graham et al.,
“Optimization and Approximation in Deterministic Sequencing”). The basic idea is that
scheduling problems are described by three variables: the nature of the machines involved,
the nature of the jobs, and the goal of scheduling. These three variables are specified in that
order, with standard codes describing factors such as precedence constraints, preemption,
release times, and the goal. For example, 1|r
j
|∑C
j
(pronounced “one-arejay-sum-ceejay”)
represents a single machine, release times, and the goal of minimizing the sum of
completion times. As Eugene Lawler recounts:
An immediate payoff was the consummate ease with which we could communicate problem
types. Visitors to our offices were sometimes baffled to hear exchanges such as: “Since one-
arejay-sum-ceejay is NP-hard, does that imply that one-preemption-arejay-sum-ceejay is NP-
hard, too?” “No, that’s easy, remember?” “Well, one-deejay-sum-ceejay is easy and that
implies one-preemption-deejay-sum-ceejay is easy, so what do we know about one-
preemption-arejay-deejay-sum-ceejay?” “Nothing.”
(In formal notation: “Since 1|r
j
|∑ C
j
is NP-hard, does that imply that 1|pmtn, r
j
|∑ C
j
is NP-
hard, too?” “No, that’s easy, remember?” “Well, 1|d
j
|∑ C
j
is easy and that implies 1|pmtn,
d
j
|∑ C
j
is easy, so what do we know about 1|pmtn, r
j
, d
j
|∑ C
j
?” “Nothing” [Lawler et al.,
“A Gift for Alexander!”; see also Lawler, “Old Stories”].)
the problem becomes intractable: In fact, it’s equivalent to the “knapsack problem,”
computer science’s most famously intractable problem about how to fill space. The
connection between this scheduling problem and the knapsack problem appears in Lawler,
Scheduling a Single Machine to Minimize the Number of Late Jobs.
a certain time to start some of your tasks: What we are calling “start times” are referred
to in the literature (we think somewhat ambiguously) as “release times.” Lenstra, Rinnooy
Kan, and Brucker, “Complexity of Machine Scheduling Problems,” showed that both
minimizing sum of completion times and minimizing maximal lateness with arbitrary