Economically Coordinated Job Shop Scheduling and Decision Point Bidding - An Example for Economic Coordination in Manufacturing and Logistics - Wolfram Conen Abstract
Furthermore, agents may represent parts of the nec-essary organizational infrastructure (namely the mani-
We discuss the application of economic coordination
fested parts of the coordination mechanism). We pri-
mechanisms to scheduling problems in manufacturing
marily use agents as a convenient metaphor for the study
and logistics. We use job shop scheduling as a sample
of coordination issues. In addition, issues relevant for
job shop problems (EJSP) which comprise valuation
an implementation of the abstract infrastructure, namely
information. We demonstrate how instances of EJSP can
computational tractability and communication complex-
be mapped to combinatorial job shop auction problems
ity, are considered. Due to the conceptual proximity of
(CJSAP). A discussion of the tractability of approaches
modeled and implemented multi-agent systems, carry-
that determine optimal solutions identifies the need
ing over some of the theoretical results to the implemen-
the merits of economic coordination with the benefits
The scenario emphasizes the relevance of the agents’
of closely domain-related solution procedures.
self-interest. We do not assume that the decision to col-
conclude that the application of newly suggested and/orwell-known economic coordination mechanisms to job
laborate with other agents implies that an agent is willing
shop and related scheduling problems in manufacturing
to reveal all his private information or that he is willing
to deviate dramatically from his utility-maximizing be-havior and turns into an altruist. The reasons for the
Keywords: Scheduling, Economic Coordination, Com-
formation of collaborations can be manifold—most rel-
evant to our analysis is the assumption that the actorsdecide to become part of the collaboration because theyconsider this to be the economically most beneficial be-
Introduction
havioral alternative, given their expectations and their at-titude towards risk. The assumption of rational behavior
The work presented in the following is based on some of
implies that the agents re-assess this evaluation continu-
the key assumptions of research in economics and game
ally and, consequently, may decide to leave the collab-
theory. A general description of the scenario under study
oration. This also explains, why an objective of the de-
sign of the coordination mechanism is to give incentivesto participate in the mechanism continually. Scenario 1. A set of actors decides to collaborate. The
Also note that this scenario is an abstraction of many
actors own a set of resources. The primary objective
real-world scenarios in logistics and manufacturing: a
of the collaboration is to utilize this set of resources as
number of units compete for the utilization of resources
economically efficient as possible. Economic efficiency
that are owned by the group of units (or by some larger
is measured in terms of money. Each actor has individ-
unit that encloses/owns the considered units). Each unit
ual preferences for resource allocations. This preference
is, to a certain extent, economically independent in its
information is (to a large extend) private to the actor—it
decisions and has information that is often not only lo-
cannot be assumed that the actors reveal their prefer-
cal but also private in the strict sense: it is only com-
ences truthfully without an incentive to do so. Paying
municated truthfully to other agents if an incentive to
tribute to the objective and the restrictions, a coordi-
do so is present. This situation can be found in virtual or
nation mechanism1 is designed to repeatedly determine
extended enterprises (consider, for example, a collabora-
allocations of the available resources to maximize effi-
tion of small and medium-size transportation companies
ciency. Each actor is free to opt out of the collaboration
with overlapping transportation capacities) or even in
if he is (repeatedly) dissatisfied with the determined out-
comparatively small production environments such as a
comes. Each actor acts rationally (within certain limi-
single workshop (groups of workers, sales people, shop-
floor managers, planners influence as actors with self-
To transfer this scenario to a multi agent setting is
interest and (conflicting) individual objectives the orga-
straightforward: Each actor or each group of actors can
be represented by a (potentially computerized) agent.
For example, if the implementation of a MAS that was
modeled as a distributed system is also distributed, the (theo-
1To explain the use of the term coordination: The mecha-
retical) communication complexity results can easily be turned
nism is executed to coordinate the interests of the actors and
into approximations for communication latency if the details of
to determine an outcome that implements a coordination of the
the underlying networking infrastructure are worked into the
behaviors of the agents—both with respect to the resources.
nization and enactment of work in the workshop). We
chose job shop scheduling as an example for this type of
with an emphasis on economics, as well as for inter-
esting and significant recent results related to both ar-
There might be more natural application areas for
eas, see (Parkes 2001) or (Wurman 1999).
value-augmented scheduling/planning problems than
instructive overview of methods and problems in the
job shop scheduling problems (JSP). However, both
wider context of self-interested agents, consider (Sand-
the inherent computational complexity and the struc-
holm 1996), whose further work, for example (Sand-
tural simplicity make job shop problems a good target
holm 2002), also contributes significantly to advances
for the demonstration of the applicability of economic
in the area. A relevant example for work related to the
coordination mechanisms to value-augmented schedul-
economics of scheduling is also the work of Wellman
ing/planning or, more general, economic resource allo-
et. al (Walsh & Wellman 1998; Wellman et al. 2001;
cation problems. Additionally, the work that has been
Walsh, Wellman, & Ygge 2000). More closely related
done in areas like holonic manufacturing call for an ap-
to the application of economic principles in manufac-
plication of the techniques that are outlined below be-
turing environments are, for example, the work of Van
Dyke Parunak (Parunak 1996) or A.D. Baker (Baker1996).3 More recently, this has also been discussed in
1. to model jobs, machines, production managers, sales
the context of new modes of manufacturing, for exam-
officers, planners etc. uniformly as autonomous, self-
ple Holonic Manufacturing, as a promising paradigm for
interested entities with individual tasks to fulfill and
controlling scheduling and planning processes in a dis-
tributed environment with local goals, private informa-
2. to study directly the economic impact of decisions
tion and general efficiency objectives (see, for example,
across all inter-related units of operations and plan-
ning (as long as the interdependencies are also
From an economic perspective, a key issue in the
mapped into the problem, which they will be if the
study of resource allocation problems is the design of
actors driving the operations get a handle to influence
decisions transparently—giving them useful budgetsand allowing for active payments is one possible way,see (Adelsberger, Conen, & Krukis 1995)).
• enable the computation of economically efficient so-
lutions. In domains where monetary valuations are
3. to apply a large number of relevant results from
available (as we assume below), this amounts to de-
game theory and microeconomics to the analysis of
termine allocations maximizing the aggregated wel-
operational and structural phenomena in manufac-
fare of the participating agents. Note that in a setting
turing/logistics systems and beyond. This includes
with private information, this requires that the mecha-
strategic considerations (with the possible goal to de-
nism gives some incentive to the agents to reveal their
sign mechanisms to give incentives to the parties in-
terested in the result to communicate their preferencestruthfully), economic efficiency (a goal can be to de-
• satisfy participation constraints for rational agents. A
sign coordination mechanisms that compute economi-
mechanism is considered to be individually rational if
cally efficient solutions), participation constraints (de-
the agents can expect participation to be beneficial. It
sign the mechanism to make sure that the participants
is also relevant that the agents are satisfied with the
feel as being treated in a fair manner to ensure their
outcome of the mechanism to ensure further partici-
pation. The question of satisfaction boils down to an-
4. to design mechanisms that scale, both vertically and
swer the question to what extend it is possible for the
horizontally, because they speak a language that is un-
agent to realize his most-preferred solution in a given
derstood at every level of a company, between com-
panies, and between companies and customers: thelanguage of value, expressed in terms of money.
In view of related work, the work presented here seemsjustified as most of the results that have been obtained
To be specific: The goal of our paper is to demonstrate
for general resource allocation problems with an em-
the applicability of economic coordination mechanisms
phasis on economics have not been specifically tailored
to economically augmented scheduling problems, and
towards shop floor and related scheduling problems in
to offer solutions for computing economically efficient
manufacturing or logistics. Furthermore, recent results
and/or straightforwardly computable heuristic solutions
in studying combinatorial auctions and exchanges show
that are tailored to the problem domain. We also discuss
that not all questions have been answered yet (relevant
some of the intricacies of economic coordination such as
work is mentioned throughout the paper). Also, eco-
strategic agent behavior, equilibrium considerations and
nomically motivated approaches in scheduling/planning
literature are sometimes difficult to analyze with respectto the key issues outlined above or tackle simplified set-
Related Work
Related work is numerous, basically all of microe-conomic literature is motivated by and related to re-
3Though the concept of (Pareto) efficiency has been intro-
source allocation problems. The study of scheduling
duced much earlier into the scheduling literature, see (Wassen-
problems in an economic context has also a significant
Overview
in P is called complete. A potential schedule is calledfeasible if (1) no first operation starts too early, (2) no
First, the basic notation and terminology for discussing
sequence constraint is violated, and (3) no overlap in the
job shop scheduling problems (JSPs) is introduced. We
processing times of assigned operations occurs on any
define the class of economically augmented job shop
machine. A schedule that is complete and feasible with
problems (EJSPs), where job agents have utility for
respect to P is called a valid schedule or a solution of P
schedules, and related them to typical minsum criteria.
We map these problem to combinatorial job shop auctionproblems (CJSAPs). We introduce prices as a means to
Definition 2 (Valid Schedule). Given an instance P of
design individually rational, economically efficient co-
JSP. A mapping s : ∪j∈J Oj → N0 is a valid schedule
ordination mechanism and discuss the issues of truthful
j ≥ rj for all j ∈ J , (2) s(oij
revelation and the Vickrey principle. We show that both
∈ J and all i ∈ {1, . . . , nj − 1}, and
EJSP and CJSAP are (strongly) NP”=hard. In view of
(3), for every pair of distinct5 operations oh, oi , either
this result, we suggest a heuristic, economically-driven
coordination mechanism that is build on top of a well-
known, domain-specific solution procedure, the Gifflerand Thompson algorithm. This decision point biddingapproach can be applied to a number of search-based
solution procedures. It is an example of an economic co-ordination mechanisms that is tailored to fit the problem
domain. This, in turn, may allow participating agents tofully comprehend and purposefully influence the execu-
tion of the mechanism by means of bidding. The paperis concluded with a brief discussion of possibilities to
extend and apply the obtained results.
Figure 1: The valid schedule (0, 2, 5)1, (0, 2, 5)2 (sched-
From Job Shop Scheduling
ules are given as nj-ary sequences of start times for each
to Economic Coordination
Scheduling allocates resources over time to enable the
We may study a problem P relative to a time horizon
execution of tasks. An important subclass of scheduling
[T S, T E], T S, T E ∈ N0 and write P [T S,TE]. The set
problems are job shop problems. The tasks are given by
of all valid schedules restricted to a specific time horizon
a set of jobs. Each job consists of a sequence of opera-
is denoted with S[T S,T E]. If the time horizon is irrele-
tions that have to be performed on specific machines in
vant, no index is shown. For a given set S, the subset Sj
a given order. We base the following on the constraint
contains all schedules that are restricted to the operation
optimization version of discrete, deterministic Job Shop
of a given job j. For a given schedule s, the subschedule
Scheduling (JSS) as defined in (Ausiello et al. 1999).4
sj denotes the elements of s that schedule operations of
Definition 1 (Job Shop Scheduling – Basic Setting). An instance of the class of job shop scheduling problems
We now turn our attention to comparisons of the qual-(JSP) consists of a set M = {1, . . . , m} of m machines,ity of schedules. Often measures that depend on the
and a set J = {1, . . . , n} of n jobs, each consisting of a
completion times of the jobs are used, for example, min-
j } of nj operations. For each suchoperation, oi , a machine mi
is the time of completion of the last operation o
j in a given (valid) schedule s. Regularly it is also as-
time pij ∈ N is given. A ready time, rj ∈ N0, denotesthe earliest possible start time for the first operation of
use derivations from this due date as a measure.
In a value-oriented business environment, this way of
In a straightforward notation, a job j is given as
measuring the quality of schedules is only convincing
if the measure has a close correspondence to the cash-
flow pattern that is induced by the imposed solutions
Example 1. Job 1: (0, [(2, 2), (1, 3), (3, 2)])
(usually, it is tried to find a solution that optimizes the
Job 2: (0, [(3, 1), (2, 2), (1, 2)])
chosen measure or that approximates an optimal solu-tion). With respect to the core measure of the success
In the following, we refer to an arbitrary, but fixed JSS
of management and operations, ie. value, such time (or
problem P . A potential schedule for a set of operations
capacity etc.) related measures can only be considered
is a mapping from the operations to start times. A poten-
as being surrogates that may render decisions intrans-
tial schedule which assigns start times to all operations
parent because they introduce incomparabilities between
4Which, in turn, is the optimization version of the decision
manufacturing shops competing for resources and give
problem SS18 as defined by Garey and Johnson in their sem-
no handle to tie local decisions to the decisions of up-
inal work (Garey & Johnson 1979) – with one difference: the
stream and downstream manufacturing/logistics units.
additional constraint of Garey and Johnson which required thateach pair of consecutive operations has to be performed on dif-
5That is, j, k ∈ J, h ∈ {1, . . . , nj}, i ∈ {1, . . . , nk} and,
This, however, would be an important prerequisite for
Definition 4 (EJSP without allocative externalities).
an unified analysis of the plans, schedules, decisions and
Let EP be given as above. EP is an EJSP without
operations of all interrelated business units.
allocative externalities iff, for any agent j and any pair
But even within one shop, it is usually not trivial to
of schedules a, b ∈ S, such that the restriction aj of a
map the goals that are related to jobs to one measure
to operations of j coincides with the restriction bj of b,
only. Some jobs may be produced directly to customer
orders (due date is important), some jobs are producedto fill up the stock (minimizing production cost is impor-
Now consider a JSS problem P and a typical minsum
tant) etc. The resulting multi-criteria problem does not
criterion (Hoogeveen, Schuurman, & Woeginger 1998),
seem to be convincingly solvable without introducing a
total job completion time. We map this J ||
unifying measure. As the value related to strategic, tac-
tic, and operational decisions determines the success of
First, determine a valid schedule by timetabling the
business operations, mapping goals to value and measur-
operations of job 1 as early as possible and without
ing quality with money is a natural choice.
slack and proceed with the operations of job 2, start-
We will now augment job shop problems with value
ing with o12 at time C1. Continue this until all opera-
information and view them as economic coordination
tions are scheduled. This produces (with effort linear in
the number of operations) a valid schedule s of lengthl =
JSPs as Economic Coordination Problems
zon [0, l] to be considered. Now, a value function v (
for each agent j can be given that determines, with ef-
Job shop scheduling problems can be extended to eco-
fort linear in the number of operations, the value of any
nomic coordination problems—the jobs are identified
with agents competing for resources. The goods to be
Function v (In: Valid Schedule s, Out: Value v)
traded are slots of machine time. To augment a JSS prob-
lem P economically, we assume that each agent has util-
ity for schedules, that is, a value function v : S
v ← l − Cj; return v;9
is available for every job agent j which assigns a non-
Proposition 5. A schedule maximizes the economic ef-
negative value to each possible valid6 schedule. ficiency in EP over all schedules in S if and only if itDefinition 3 (EJSP). An instance P (possibly restricted minimizes the minsum criterion total completion time10
to a time horizon) of the class JSS of job shop schedulingin P over all schedules in S.problems and a set V of j value functions v : S
one for each job j, defines an instance EP of the class ofProof. Let s be a schedule that maximizes efficiency in
economically augmented job shop scheduling problems
EP . Assume that s does not minimize the total com-
pletion time in P , that is, there is a schedule r ∈ S
The general objective of solving EJSPs is to select a
schedule from the set of possible valid schedules that
9Note that this transformation is polynomial because it
makes use of the fact that there is significant structure in the
Would we have to enumerate all (or almost all)
schedule/value pairs explicitly, the transformation would not
As we show below, this class of scheduling problems en-
be polynomial. However, criteria that would require such an
compasses a number of traditional job shop scheduling
effort are virtually never used in scheduling literature (they
problems. To do so, we first consider a restricted vari-
would be random in the sense of algorithmic complexity the-
ant of the EJSP, where, for each agent j, the value of a
schedule does only depend on the operations in O
Similar results can be obtained for restrictions to other
the general variant, an agent j may value two schedules
minsum criteria (e.g., total tardiness, weighted total comple-tion/tardiness, holding costs, early/tardy penalties). Note also,
differently though both assign the same start times to the
that EJSP without allocative externalities cannot model criteria
operations in Oj. For example, this allows an agent k to
like Cmax, because a global optimum for the desired criterion
express that she prefers if a machine, say 2, is assigned
is not obtainable from local considerations. The jobs cannot be
to agent l instead of agent m in the interval [3, 5]. This
modeled as being independent in this case. If the value func-
tion should reflect the benefit of achieving a minimal Cmax,they must reflect this dependency in their valuation of sched-
6It can also be useful to consider incomplete feasible sched-
ules, or otherwise, self-interest prevents the optimization of the
desired criterion. For Cmax, the jobs should value schedules
7Remember that S is the set of all valid schedules that solve
with an earlier completion time for all jobs higher than, for
P . If a time horizon is given, this set may be empty. If no time
example, schedules that give them an earlier individual com-
horizon is given, the set is countably infinite. We will therefore
pletion time (the time the last operation of j finishes) but a
usually assume that a time horizon is given (without displaying
later overall completion time (the time the last job finishes)—
in other words, the value of a schedule does not only depend
8Though, to map a very common objective, namely max
on the operations in Oj but on all (final) operations (that is,
completion time, it is required, see the footnote below.
allocative externalities are present).
(l − r(o j ) + p j ), or, written differently,
exists such that the schedule s is covered by the unit in-
tervals in B (ie., A(s) ⊆ B), the value of B is set to
the value (in the underlying EJSP) of the best schedule
among the covered schedules, that is, vj(B) = v∗(B)
contradicting the assumption. The other direction fol-
ule is covered by B, vj(B) is set to 0. Proposition 6. EJSPs are NP-hard in the strong sense. Proof. As above proposition shows, EJSP can be re-
is polynomial (see above). From the strong NP-hardness
Cj (s. (Lawler et al. 1992) or (Hoogeveen,
Schuurman, & Woeginger 1998)) the proposition fol-lows.
To adapt the problem to our economic setting with
self-interested, (bounded) rational agents, the followingassumption are necessary.
Figure 2: The unit intervals (or time slots) of example 1.
In line with our basic motivation, we assume that the
value function is information private to the agent, thatis, no (central) institution has access to this informationwithout prior consent of the agent. In addition, utilityExample 2. Reconsult example 1. is transferable11 between agents (ie, a meaningful cur-
to be considered is [0, 9].
rency has to be available to express valuations and to
tion leads to the preference relations, which underly thevalue functions: let j be a job agent and s1 and s2 be
We also assume that no agent can be forced to act
schedules which are complete with respect to j. If the
against his will. With these assumptions, we can trans-
last operation of agent j in s1 is completed earlier than
late economically augmented job shop scheduling prob-
s2, agent j prefers schedule s1 (written as s1
lems to a specific subclass of combinatorial auction
the completion times are equal, the agent is indifferent
problems (CAPs), which are currently studied exten-
between s1 and s2 (written as s1 ∼ s2).
sively in AI and microeconomic literature (s. (de Vries
For agent 1 the preference relation given below fol-lows. for convenience, a rank is assigned to the equiva-lence classes of equally preferred schedules.Transforming EJSP to CJSAP 1: (0, 2, 5)2: (0, 2, 6), (0, 3, 6), (1, 3, 6)
Let EP be in EJSP and let [T S, T E] be a time horizon. 3: (0, 2, 7), (0, 3, 7), (0, 4, 7), (1, 3, 7), (2, 4, 7)
An economic coordination problem can now be formu-
Agents: A set of n job agents, N = J = {1, . . . , n},
For agent 2, the preference relation is only partially dis-
and an arbitrator, 0. The arbitrator is modeled as a sup-plier. The job agents are modeled as consumers. Goods: The set of goods, Ω, is the set of all machine-
2: (0, 1, 4), (0, 2, 4), (1, 2, 4)
specific unit intervals within the time horizon (remember
3: (0, 1, 5), (0, 2, 5), (0, 3, 5), (1, 2, 5), (1, 3, 5), (2, 3, 5)
Ω = {[z, z + 1]i | i ∈ M ∧ z = T S, . . . , T E − 1}
Agent 1 values the earliest possible completion (at 7)with 20 currency units (CU) and agent 2 (at 5) with 16
Any subset B ⊆ Ω (alternatively writable as B ∈ 2Ω,
CU. a delay per time unit reduces the value of the sched-
the power set of Ω) is called bundle. ule for agent 1 by 3 CU and for agent 2 by 2 CU, result-
Before we can define value functions, a function A :
ing in the following functions vR(·), which assign values
S → 2Ω that partitions a schedule s into the covered
machine-specific unit intervals is required (note that s isa function, and thus a relation, so that it is appropriate to
write (o, t) ∈ s instead of t = s(o)). For a given bundle B, its valuation can be determinedby mapping B with a function r to the preference rankValue functions: The value function of consumer j,
which corresponds to the best schedule which is cov-
vj : 2Ω → N0 is defined as follows: if at least one s ∈ S
For example for the largest bundle, Ω,which covers all schedules that lie within the time hori-
Technically, the value functions have to be quasilinear
zon, rank 1 is the result of the mapping for both agents,
in money, compare, for example, (Mas-Colell, Whinston, &Green 1995). Quasilinearity allows to interpret the utility for a
that is v1(Ω) = vr(r(Ω)) = vr(1) = 20
good (time slots in our case) as the willingness to pay for it. Proposition 7 (Monotony, Free Disposal). vi(A) Proposition 10. For any EP ∈ EJSP, if a valid sched-
vi(B) for all A ⊆ B ⊆ Ω, i ∈ N .ule exists, a solution of the corresponding problem C ∈CJSAP can be transformed into an optimal schedule forProof. This follows immediately from the construction
the original, economically augmented job shop schedul-
of the value functions: a bundle B that contains at least
ing problem EP (and vice versa).
as many unit intervals as a bundle A covers at least theschedules that A covers, thus its value cannot be smaller
Proof. Let X = (X0, X1, . . . , Xn) be a tight solution13
than the value of A because the maximum value over
of C. Construct a schedule sX from X as follows: for
all covered schedules in the EJSP instance is at least as
each agent j ∈ J, find the best schedule sX that is cov-
ered by Xj by simply timetabling the operations as unitintervals are available (due to the tightness of X, this is
This is sometimes also called Free Disposal because
possible in cost linear to the number of time slots in X).
adding further unit intervals will not reduce value, or,
Combine the schedules sX to the schedule sX . Note that
in other words, superfluous goods can be disposed off at
the construction of C ensures that this construction is al-
ways possible if a valid schedule exists. Furthermore,
We also assume that no budget restrictions exist: every
as the allocation X is a partition of Ω, no overlap on a
consumer j is in possession of enough money to be able
machine can occur. The other direction is even simpler:
to pay up to the amount of the valuation for his most
each reservation for an operation in the optimal sched-
preferred bundle. The consumers have no endowment
ule can be split into the machine-specific unit intervals.
beyond money. All goods belong to the arbitrator. If the
The information in the schedule can be used to assign
consumer does not receive any good, his utility shall be
the unit intervals immediately to the correct part of the
allocation (cost linear to the processing time).
The objective of the allocation of the goods (from the
perspective of the arbitrator) is to maximize the aggre-
We will now turn our attention to the problems related
gated utility of the consumers. Here, this directly cor-
to finding an efficient allocation. They can be outlined
responds to maximizing the sum of individual utilities.
as follows: (1) a certain amount of value information is
An allocation12 X∗ = (X∗, . . . , X∗)
necessary to determine an efficient allocation; (2) once
objective if and only if the allocation is efficient, that is,
the required information is available, the actual compu-
X∗ has to be a maximizer for the following problem
tation has to be performed; (3) an incentive has to begiven to the agents to report their part of the required in-
formation truthfully, or otherwise, efficiency of the solu-
vj(Xj) (X iterates over all allocations) (2)
tion cannot be guaranteed; and (4) the agents have to be
satisfied with the determined outcome. We neglect issue(1), briefly discuss issue (2) and concentrate on (3) and
Example 3. For the above example, the following allo-
(4). We will, however, return to the issue of complexity
X1 ⊇ {[0, 1]2, [1, 2]2, [2, 3]1, [3, 4]1, [4, 5]1, [5, 6]3, [6, 7]3}X2 ⊇ {[0, 1]3, [2, 3]2, [3, 4]2, [5, 6]1, [6, 7]1}X
Determination of Efficient Allocations Consecutive unit intervals can be consolidated to bun-
If we assume for now that the (complete and true) valuefunctions of all agents are known, an efficient allocation
of the unit intervals to the job agents can be computed
with one of the well-studied methods of winner deter-
mination (compare (Sandholm 2002; Sandholm et al.Definition 8 (CJSAP). Let EP be an instance of EJSP.
2001; Fujishima, Leyton-Brown, & Shoham 1999)). To
The sets Ω and N , the value functions vj(·) of the con-
save communication, approaches have been suggested
sumers that are obtained by the above transformation of
that only partially reveal the value functions of the con-
EP , and the objective (2) of the arbitrator define an in-
sumers (compare (Parkes 2001) for indirect, iterative
stance C of the class of Combinatorial Job Shop Auction
auctions and (Conen & Sandholm 2002b) for a progres-
sive direct mechanism based on (Conen & Sandholm
We call an allocation that conforms to the objective of
problem is essentially a set-packing problem (Rothkopf,Pekeˇc, & Harstad 1998; de Vries & Vohra 2001) and
Proposition 9. A solution exists for every possible in-
that it is NP-hard. We show below that this also holds
Proof. This follows with a straightforward combinato-
13A tight solution is a solution that does not contain time
rial argument immediately from the finiteness of the
slots that are not used. Note that a tight solution always exists
problem (which we assume throughout the paper).
because the value of a bundle is the value of the best coveredschedule, and, in consequence, the bundle that covers just the
12That is an (n + 1)-ary partition of the set of goods, Ω,
best schedule, is tight and optimal (that is: unused slots cannot
which assigns to agent j the goods in the bundle Xj (some Xj
add to the value of a bundle due to the construction of the value
may be empty, so it is not a partition with non-empty subsets,
functions). Further note that is it always possible to tighten a
solution with costs less than exponential. Example 4. Bundles on offer in the efficient allocation:
In the above example, two core problems remain: first,
because only agent 1 can realize his best alternative,
agent 2 will envy him. Second, we have tacitly assumed
that the agents report their utility truthfully—but whyshould they do so under our assumption of preferences
being private information? Certainly, agent 2 could ex-
pect to benefit from over-exaggerating his valuations.
If agent 1 would expect agent 2 to over-exaggerate, he
Vickrey Payments (the vector of payments also fulfill the
would do the same, and so forth. Without an additional
equilibrium condition if interpreted as prices for the
way to ensure satisfaction and to make lying unattrac-
bundles instead of personalized payments):
tive, we cannot expect to compute allocations that areefficient with respect to the true preferences. The way
to go is to introduce prices. Each consumer has a net
utility function which reflects the impact of prices (neg-
ative transfers in the following definition) on the realiz-
The payments ensure that there is no (individual) incen-Definition 11 (Net utility). The net utility function tive for the agents to lie, as can be seen as follows. Firstnote that the price each agent has to pay does only de-
j (·) : 2Ω × Z → Z for each consumer j is definedpend on the reported utilities of the competing agents—it represents the loss of utility that the other agents ex-
To keep every consumer satisfied with the outcome
periences due to the participation of the former agent.
(consisting of allocation and payment), uj(Xj, p) ≥
Now, assume that agent 1 would underbid his valuation
ui(A, p) must hold for every consumer j and every bun-
with, say, 17. Then he risks that agent 2 (or any other
dle A ⊆ Ω,that is, the net utility of the bundle he re-
agent) would bid just above 17 but below 20, say 18,
ceives must be at least as good as it would be for any
and would thus receive the good. As the price he has
other bundle at the given prices (or, otherwise, the con-
to pay is independent of his own bid and will equal the
sumer would prefer to receive the bundle that gives him
bid of the other agent, he could have done better by bid-ding truthfully (exactly 2 = 20 - 18 instead of 0). If he
This leads immediately to the notion of equilibria. An
would have known beforehand what the other agent will
outcome, that is, an allocation and a payment vector (de-
bid, say x, he would not have a reason to underbid ei-
termined by the prices), is an equilibrium if both sides
ther, because there would be no difference in net value
of the market are satisfied with it (the market is cleared). for agent 1 in bidding 20 or x +
In our case this is true if the above condition holds for
the bid of the other agent anyway). He would also not
all consumers and if the allocation is efficient (to sat-
overbid, because he risks that he receives the overbid-
isfy the supplier). There are different restrictions that
ded bundle for a price between his true valuation and
one can impose on prices—prices for bundles have to
his bid and would, thus, realize a loss. If he would over-
be the sum of prices for individual goods (see (Gul &
bid in the fully-informed situation, he cannot gain any
Stacchetti 1999; Kelso & Crawford 1982), prices are in-
net value from it either. An analogous reasoning applies
dependent for every bundle (see (Wurman & Wellman
to agent 2, thus both agents will not have an incentive
2000)), prices are determined for the bundles in the effi-
to misrepresent their valuation if they act rational (this
cient allocation and prices for bundles of these bundles
corresponds to an equilibrium in dominant17 strategies).
are additive (see (Conen & Sandholm 2002a)). Only theindependent pricing of all bundles can guarantee the ex-
The general principle invoked here has been mentioned
istence of equilibrium price vectors. However, imple-
in the example: the payments that an agent has to trans-
menting the determined outcome may require enforce-
fer do not depend on her own bid but captures instead
ment.15 For the more natural pricing modes, equilibrium
the effect of her participation on the other participating
price vectors need not exist.16 We will therefore not
agents.18 It is intuitively clear that, as soon as there is a
discuss (anonymous) equilibrium pricing in detail and
dependency for a bundle Xj between the reported util-
turn our attention to a solution concept for which solu-
ity of agent j and the price j has to pay, j will have an
tions always exists: Vickrey payments. We will demon-
incentive to minimize this price by misrepresenting his
strate in the example below that implementing Vickrey
utility if possible. To do so, he might start to collect in-
payment-based coordination mechanisms give the par-
formation about the other participating agents (which is
ticipating agents no incentive to lie (a very relevant de-
not necessary above) to become able to behave strategi-
sign objective in a private information setting). Please,
cally. This, in turn, may make it impossible for the ar-
consider the continued example below.
bitrator to pick the efficient allocation—all that he coulddo would be to pick the allocation that is efficient with
14Note, that we make the usual assumption of quasi-linearity
respect to the reported utilities. This brief digression
into the issue of incentive compatibility may suffice to
15Each agent is only allowed to buy one bundle—thus, if
he is interested in AB and we have p(AB) = 6, p(A) = 2,
17Weakly dominant in the case of informed agents.
p(B) = 2, he would want to enter the auction with two identi-
18The principle has been discovered and applied indepen-
dently by Vickrey (in 1961), Clarke (in 1971) and Groves (in
16This negative result holds also for instances of CJSAP.
1973) (see, for example, (Vickrey 1961)).
demonstrate one of the most prevalent problems in envi-
It is the nature of any heuristic modification that no
ronments where the agents have private information: the
guarantee to obtain economically efficient solutions can
problem of eliciting their preference truthfully to allow
be given. Furthermore, other desirable properties like
incentive-compatibility may get lost. With respect to aspecific problem domain, it seems reasonable to postu-
Proposition 12 (Existence of Vickrey Outcome).
late that the heuristic reflects the properties of the do-
An outcome consisting of an efficient allocation and
main naturally, allowing users to make justifiable deci-
a vector of related Vickrey payments exists for every
sions when dealing with the heuristic mechanisms. We
suggest a mechanisms that is closely related to a straight-
Proof. (Sketch) The proof follows from a straightfor-
forward solution procedure for job shop scheduling,
ward combinatorial argument: with finite sets of bundles
namely the algorithm of Giffler and Thompson (GT). It
and agents. A computable solution of the maximization
allows the agents (resp. the represented actors) to base
problem (2) (to determine the efficient allocation) and
their bidding behavior on an understanding of the con-
the n (or less) maximization problems following from
sequences of decisions that are made along an execution
the initial problem by leaving out, for each non-empty
bundle in the allocation, the agent that receives it (to de-termine the effect of his participation, that is the Vickrey
Decision Point Bidding
payments), is immediately available from enumeratingall possible complete and reduced allocations and pick-
Most solution procedures for JSPs (or for other resource
allocation problems) can be viewed as a sequence ofdecisions—for the GT, this is the selection of the next
Complexity Issues
operation to schedule. Now, instead of competing forreservations directly, the agents bid for the right to stip-
Two immediate problems of auction mechanisms that try
to solve a CJSAP are (1) that the mechanisms may re-
As GT constructs an active schedule, we will restrict
quire communication that is exponential in the number
our analysis to problem instances of EJSP that have the
of unit intervals (compare the general result of (Nisan
property that the individual agents always (weakly) pre-
& Segal 2002), which extends to CJSAP) and (2) that
fer earlier allocation of the final operation (to mimic the
solving the actual allocation problem once all required
value information is received is NP-hard, as the follow-
We give a brief re-collection of the GT prior to outlining
a coordination mechanism that allows to solve restrictedEJSP by following the sequence of decisions that are
Corollary 13. CJSAPs are NP-hard in the strong sense.
characteristic for an execution of GT. Assume that aninstance EP of EJSP is given. Proof. This follows immediately from Proposition 6 andthe polynomiality of the transformation given in Propo-
(1) Initialize the set SO of schedulable operations to
Note also that CJSAP is a subclass of the combinato-
Determine the decision set DS by first picking
rial auction problem CAP which is equivalent to maxi-
from SO one of the operations with the earliest
mum weighted set-packing (compare (de Vries & Vohra
Consequently, we cannot expect to obtain optimal so-
lutions for problems of reasonable size with reasonable
insert into DS all operations from SO that re-
computational efficiency. Furthermore, the approxima-
quire myx and start before the potential comple-
bility results obtained for maximum weighted set pack-
ing (Ausiello et al. 1999) are not very encouraging. We
(Decision Point) Choose one of the operations
also do not expect that CJSAP is an especially well-
from DS, say oba and make reservations cor-
behaved subclass in this respect due to its proximity to
responding to its related ready and processing
EJSP and, thus, typical job shop scheduling problems.
Update the ready time information of all jobs
We can now try to modify auction mechanism that deter-
mine efficient allocations (like iBundle (Parkes & Ungar
2000) or AkBA (Wurman & Wellman 2000)) to relax the
add its successor (if it exists, ie. if b < n
efficiency goal and to restrict the search space heuristi-
cally. However, we cannot expect this to be easily justi-fiable with respect to the properties of the initial problem
Now, the basic mechanism is as follows: the arbitrator
announces to run a GT and starts to ask the agents for
information about ready times and about the process-
For pointers to recent work, see (Bikhchandani et al.
ing times of the operations to be scheduled. It iterates
20If we allow partially ordered sequences of operations and
the Giffler and Thompson procedure as usual, request-
alternative routings, the corresponding variant of EJSP and the
ing bids from the agents to be able to determine a decider
resulting CJSAP could be mapped to the general combinatorial
for each decision point (see above). Each agent who has
currently an operation in the decision set is entitled to
bid. The winner will pay the price of the second highest
to numerous, decision-based solution procedures. Note
bid and receives, as a result, the earliest possible reser-
that obtaining analytical results will not be an easy task,
vation of his operation in the decision set (ties in the bids
however, advancing this concept looks promising to us
due to the similitude of mechanism and domain-specificproblem structure. Corollary 14. For any finite EJSP, the mechanism ter- minates and the resulting allocation corresponds to an active schedule. Discussion
This follows immediately from the construction of themechanism, which follows the execution pattern of the
This paper has discussed economically augmented job
GT and, thus, inherits its property of computing an ac-
shop problems and their transformation into a specific
subclass of combinatorial auction problems. We have
Proposition 15. For the restricted EJSP, the set of pos-
briefly discussed the problem of finding efficient solu-
sible outcomes of the mechanism contains an efficient
tions and of doing this in a way to ensure that the agents
participate and report their valuations truthfully. Moti-vated by problems of computational efficiency, we have
suggested to combine domain-related decision making
to bid on in each run of the mechanism. The sequence
procedures with bidding. This hybrid approach results
of decisions can be described by a z-ary vector of job
in a heuristic that, while remaining problem driven, is
agent indices. The set of all sequences that lead to active
applicable in the context of self-interested agents with
schedules can be obtained through iterated 0-bidding
private information. We consider the study of such ap-
(no agent bids a non-zero amount of currency units in
plication scenarios in the context of scheduling for man-
any iteration). This is due to the non-deterministic tie-
ufacturing and logistics as important due to the increas-
breaking and the fact that the mechanism follows the ex-
ing tendencies to (1) restructure companies towards col-
ecution path of GT and thus inherits the property of GT
laborations of (semi-)autonomous units on all levels of
to generate all active schedules if all decisions are taken
granularity and to (2) form (potentially) volatile col-
in every possible way. The proposition follows from an
laborations between autonomous enterprises. In both
adaptation of Theorem 2.1 of (French 1982) (suggested
cases, monetarian value may turn out to be a key issue
by French in Chap. 10), which states that the class of ac-
for the integration of diverging interests—economically
tive schedules contains the optimal schedule for regular
efficient mechanisms that keep the participating agents
measures, and the fact that the restricted EJSP mimics a
individually satisfied can contribute to this integration
without violating autonomity and information privacymore than necessary.
Note that each bidding decision is necessarily based oncalculations of the expected value of a positive decision(the agent wins the decision point). Each agent knows
Extensions and future work
beforehand that he has to win exactly nj decision points.
The mapping of economic job shop problems to com-
He can also calculate the influence of each taken de-
binatorial auction problems can easily be extended to
cision on the maximally achievable utility (simply by
accommodate other classes of job shop problems, for
assuming that he will win all following decision points
example problems with alternative routings, reservation
up to and including an allocation for his last operation,
costs for resources, or sequence-dependent set-up costs.
which fixes the reservation times for all remaining oper-
Further effort is necessary to explore the options and
ations and, thus, allows us to set a precise upper bound
consequences of decision point bidding, with respect to
on the realizable utility). His attitude towards risk will
both a theoretical analysis of its effect on efficiency,
influence his bidding decisions, as will his knowledge
strategic behavior etc. and a practical or experimental
about the bidding behavior of competing agents in this
analysis of its applicability. It will also be interesting
or in prior runs of the mechanism (if agents participate
to apply the basic concept of decision point bidding to
in multiple allocation problems).22 A solution concept
other solution procedures for resource allocation prob-
to study such situations is known as Bayes-Nash Equi-
librium, though this is not discussed here. Let us onlypoint out that augmenting solution procedures that showa natural fit to the problem domain may be an interest-
References
ing opportunity to design economic coordination mech-anism that are easily understandable for the participat-ing agents and that give the agents a direct handle to
Adelsberger, H. H., and Conen, W. 2000. Economic
use their understanding to influence the outcome of the
coordination mechanisms for holonic multi agent sys-
mechanism. The decision point approach can be applied
tems. In Proc. of HoloMAS Workshop, DEXA 00.
Adelsberger, H. H.; Conen, W.; and Krukis, R. 1995.
21Instead of the sealed-bid second-price auction suggested
Scheduling utilizing market models. In Proc. of the
here, an open-cry English auction could be chosen, which
ICCIM 95. Singapore: World Scientific.
would convey more information about the competitors to theagents.
Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.;
22The mechanism can be extended to resale to take limited
Marchetti-Spaccamela, A.; and Protasi, M. 1999. Com-plexity and Approximation. Springer.
Baker, A. 1996. A case study where agents bid with
Parkes, D., and Ungar, L. 2000. Iterative combinatorial
actual costs to schedule a factory. In Clearwater, S. H.,
auctions: Theory and practice. In Proc. of the AAAI-00.
ed., Market-Based Control. Singapore: World Scien-
tions: Achieving Economic and Computational Effi-
Bikhchandani, S.; de Vries, S.; Schummer, J.; and
ciency. Ph.D. Dissertation, Computer and Information
Vohra, R. V. 2001. Linear programming and Vickrey
Sciences, University of Pennsylvania.
Parunak, H. V. D. 1996. Applications of distributed
artificial intelligence in industry. In O’Hare, G., and
elicitation in combinatorial auctions. In Proc. of the
Jennings, N., eds., Foundations of Distributed ArtificialACM E-commerce conference (ACM-EC01). Tampa,
Intelligence. New York: Wiley. 139–164.
Rothkopf, M. H.; Pekeˇc, A.; and Harstad, R. M. 1998.
Conen, W., and Sandholm, T. 2001b. Minimal prefer-
Computationally manageable combinatorial auctions.
ence elicitation in combinatorial auctions. In IJCAI-Management Science 44(8):1131–1147. Early version:
2001 WS on Economic Agents, Models, and Mecha-
Rutgers Center for Operations Research technical re-
Conen, W., and Sandholm, T. 2002a. Coherent pricing
Sandholm, T.; Suri, S.; Gilpin, A.; and Levine, D.
of efficient allocations in combinatorial economies. In
2001. CABOB: A fast optimal algorithm for combina-
Prooceddings of the AAAI-02 Workshop on Game the-
torial auctions. In Proceedings of the Seventeenth In-oretic and Decisiosn Theoretic Agents (GTDT-02). ternational Joint Conference on Artificial Intelligence
Conen, W., and Sandholm, T. 2002b. Partial-revelation
VCG mechanism for combinatorial auctions. In Pro-
Sandholm, T. 1996. Negotiation among Self-Interestedceddings of the National Conference on Artificial Intel-Computationally Limited Agents. Ph.D. Dissertation,
University of Massachusetts, Amherst.
de Vries, S., and Vohra, R. 2001. Combinatorial auc-
http:// www.cs.cmu.edu/ ˜sandholm/ dissertation.ps.
tions: A survey. Draft of 25. Oktober 2001.
Sandholm, T. 2002. Algorithm for optimal winner de-
French, S. 1982. Sequencing and Scheduling. Ellis
termination in combinatorial auctions. Artificial Intel-
Fujishima, Y.; Leyton-Brown, K.; and Shoham, Y.
Vickrey, W. 1961. Counterspeculation, auctions, and
1999. Taming the computational complexity of com-
competitive sealed tenders. Journal of Finance 16:8–
In Proceedings of the Sixteenth Interna-
Walsh, W., and Wellman, M. 1998. A market proto-
tional Joint Conference on Artificial Intelligence (IJ-
col for decentralized task allocation. In Proceedingsof the Third International Conference on Multi-Agent
Garey, M. R., and Johnson, D. S. 1979. Computers andIntractability. W. H. Freeman and Company.
Walsh, W.; Wellman, M.; and Ygge, F. 2000. Combi-
Gul, F., and Stacchetti, E. 1999. Walrasian equilib-
natorial auctions for supply chain formation. In ACM
rium with gross substitutes. Journal of Economic The-Conference on Electronic Commerce 2000: 260-269.
Wassenhove, L. V., and Gelders, L. 1980. Solving a
Hoogeveen, H.; Schuurman, P.; and Woeginger, G.
bicriterion scheduling problem. Eur.J. Opl. Res. 4:42–
Non-approximability results for scheduling
problems with minsum criteria. In Bixby, R. E.; Boyd,
Wellman, M.; Walsh, W.; Wurman, P.; and MacKie-
E. A.; and Rios-Mecado, R. Z., eds., Proceedings of the
Mason, J. 2001. Auction protocols for decentralized
6th Conference on Integer Programming and Combina-
scheduling. Games and Economic Behavior 35:271–
torial Optimization,, number 1412 in LNCS, 353–366.
Wurman, P. R., and Wellman, M. P. 2000. AkBA: A
Kelso, A. S., and Crawford, V. 1982. Job matching,
progressive, anonymous-price combinatorial auction.
coalition formation, and gross substitues. Economet-
In Proceedings of the ACM Conference on Electronic
Lawler, E.; Lenstra, J.; Kan, A. R.; ; and Shmoys, D. Sequencing and Scheduling: Algorithms andMultidimensional Design Auction for ComputationalComplexity, volume 4 of Handbooks in Operations Re-Economies. Ph.D. Dissertation, Computer Science and
search and Management Science. North-Holland.
Engineering, University of Michigan.
Li, M., and Vitanyi, P. 1997. An Introduction to Kol-mogorov Complexity and Its Applications. Springer,2nd edition edition. Mas-Colell, A.; Whinston, M.; and Green, J. R. 1995. Microeconomic Theory. Oxford University Press. Nisan, N., and Segal, I. 2002. The communicationcomplexity of efficient allocation problems. Workingpaper.

COLONOSCOPY PREPARATION with MIRALAX AND GATORADE® Physician: Rosemarin Procedure Date ________________ Time________ Arrival Time________ Your procedure is scheduled at New York Endoscopy Center located at Two Gannett Drive, on the First Floor in Suite 104. We are located in White Plains, NY however if you are using a navigation system you may need to enter West Harrison as

■ Overview: What goes up, mustcome down. It’s an old story, but nevermore unwelcome than today, as legionsof baby-boomer males (and evenpost-baby-boomers) confront theirdeclining virility and sexual potency. That’s why Viagra®cological gold as soon as it hitpharmacies in 1998. Then it wentplatinum, as Viagra became a franchise builderfor Internet pharmacies. And faster than you can