 Cost sharing in a job scheduling problemDebasis Mishra and Bharath Rangarajan No 2005053, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Abstract: A set of jobs need to be served by a server which can serve only one job at a time. Jobs have processing times and incur waiting costs (linear in their waiting time). The jobs share their costs through compensation using monetary transfers. In the first part, we provide an axiomatic characterization of the Shapley value rule by introducing some fairness axioms that are new in the literature. In the second part, we use linear programming duality to provide an alternate characterization of the Shapley value rule. Here, we use the idea of decomposition of transfers and the notion of pairwise no-envy allocation. Of the family of allocation rules that satisfy pairwise noenvy, the Shapley value rule is the one with the minimum sum of absolute values of transfers. We discuss no-envy rules and show that no-envy is not possible in general. If processing times of all jobs are equal, then it is possible to design no-envy rules, and we characterize all no-envy rules for this case. Keywords: queueing problems; Shapley value; cost sharing; job scheduling (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2005053 Access Statistics for this paper More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC. |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.