Homepage.informatik.fh-gelsenkirchen.de

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 such operation, 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, denotes the 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 it Definition 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 scheduling in 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 of Proof. 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, utility Example 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 the value 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 determined by mapping B with a function r to the preference rank Value 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 for Proof. 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. First note that the price each agent has to pay does only de- j (·) : 2Ω × Z → Z for each consumer j is defined pend 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 Artificial ACM 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-Interested ceddings 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 Proceedings of the Third International Conference on Multi-Agent Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability. 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 and Multidimensional Design Auction for Computational Complexity, 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.

Source: http://homepage.informatik.fh-gelsenkirchen.de/conen/paper/conen-scheduling-auctions.pdf