IDEAS home Printed from https://ideas.repec.org/a/spr/comaot/v6y2000i2d10.1023_a1009637419820.html
   My bibliography  Save this article

Nondominated Schedules for a Job-Shop with Two Competing Users

Author

Listed:
  • A. Agnetis

    (Università di Siena)

  • P.B. Mirchandani

    (The University of Arizona)

  • D. Pacciarelli

    (Università di Roma Tre)

  • A. Pacifici

    (Università di Roma “Tor Vergata”)

Abstract

We consider the scenario where two users compete to perform their respective jobs on a common set of resources. The job for each user has a due-date and the cost function associated with the due-date is quasi-convex (i.e., it has a single local minimum). We characterize the set of nondominated schedules over which the users may negotiate and develop a polynomial algorithm to find this nondominated set.

Suggested Citation

  • A. Agnetis & P.B. Mirchandani & D. Pacciarelli & A. Pacifici, 2000. "Nondominated Schedules for a Job-Shop with Two Competing Users," Computational and Mathematical Organization Theory, Springer, vol. 6(2), pages 191-217, July.
    • Handle: RePEc:spr:comaot:v:6:y:2000:i:2:d:10.1023_a:1009637419820
    DOI: 10.1023/A:1009637419820
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1023/A:1009637419820
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1023/A:1009637419820?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Sheldon B. Akers & Joyce Friedman, 1955. "A Non-Numerical Approach to Production Scheduling Problems," Operations Research, INFORMS, vol. 3(4), pages 429-442, November.
    2. Nicholas G. Hall & Wieslaw Kubiak & Suresh P. Sethi, 1991. "Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date," Operations Research, INFORMS, vol. 39(5), pages 847-856, October.
    3. David Kraay & Patrick T. Harker & Bintong Chen, 1991. "Optimal Pacing of Trains in Freight Railroads: Model Formulation and Solution," Operations Research, INFORMS, vol. 39(1), pages 82-99, February.
    4. Nicholas G. Hall & Marc E. Posner, 1991. "Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date," Operations Research, INFORMS, vol. 39(5), pages 836-846, October.
    5. Włodzimierz Szwarc, 1960. "Solution of the Akers-Friedman Scheduling Problem," Operations Research, INFORMS, vol. 8(6), pages 782-788, December.
    6. William W. Hardgrave & George L. Nemhauser, 1963. "A Geometric Model and a Graphical Algorithm for a Sequencing Problem," Operations Research, INFORMS, vol. 11(6), pages 889-900, December.
    7. S.J. Rassenti & V.L. Smith & R.L. Bulfin, 1982. "A Combinatorial Auction Mechanism for Airport Time Slot Allocation," Bell Journal of Economics, The RAND Corporation, vol. 13(2), pages 402-417, Autumn.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Perez-Gonzalez, Paz & Framinan, Jose M., 2014. "A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems," European Journal of Operational Research, Elsevier, vol. 235(1), pages 1-16.
    2. Tifenn Rault & Faiza Sadi & Jean-Charles Billaut & Ameur Soukhal, 2024. "Scheduling two interfering job sets on identical parallel machines with makespan and total completion time minimization," Journal of Scheduling, Springer, vol. 27(5), pages 485-505, October.
    3. Donatas Elvikis & Vincent T’kindt, 2014. "Two-agent scheduling on uniform parallel machines with min-max criteria," Annals of Operations Research, Springer, vol. 213(1), pages 79-94, February.
    4. Yunqiang Yin & T. C. E. Cheng & Du-Juan Wang & Chin-Chia Wu, 2017. "Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs," Journal of Scheduling, Springer, vol. 20(4), pages 313-335, August.
    5. Zhenyou Wang & Cai-Min Wei & Yu-Bin Wu, 2016. "Single Machine Two-Agent Scheduling with Deteriorating Jobs," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(05), pages 1-17, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    2. Y N Sotskov & A Allahverdi & T-C Lai, 2004. "Flowshop scheduling problem to minimize total completion time with random and bounded processing times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(3), pages 277-286, March.
    3. X. Cai & F. S. Tu, 1996. "Scheduling jobs with random processing times on a single machine subject to stochastic breakdowns to minimize early‐tardy penalties," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(8), pages 1127-1146, December.
    4. Li, Y. & Ip, W. H. & Wang, D. W., 1998. "Genetic algorithm approach to earliness and tardiness production scheduling and planning problem," International Journal of Production Economics, Elsevier, vol. 54(1), pages 65-76, January.
    5. Agnetis, Alessandro & Kellerer, Hans & Nicosia, Gaia & Pacifici, Andrea, 2012. "Parallel dedicated machines scheduling with chain precedence constraints," European Journal of Operational Research, Elsevier, vol. 221(2), pages 296-305.
    6. Philip Kaminsky & Onur Kaya, 2008. "Scheduling and due‐date quotation in a make‐to‐order supply chain," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(5), pages 444-458, August.
    7. Brewer, Paul J. & Plott, Charles R., 1996. "A binary conflict ascending price (BICAP) mechanism for the decentralized allocation of the right to use railroad tracks," International Journal of Industrial Organization, Elsevier, vol. 14(6), pages 857-886, October.
    8. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    9. Ali Kordmostafapour & Javad Rezaeian & Iraj Mahdavi & Mahdi Yar Farjad, 2022. "Scheduling unrelated parallel machine problem with multi-mode processing times and batch delivery cost," OPSEARCH, Springer;Operational Research Society of India, vol. 59(4), pages 1438-1470, December.
    10. Feifeng Zheng & E. Zhang & Yinfeng Xu & Wei-Chiang Hong, 2014. "Competitive analysis for make-to-order scheduling with reliable lead time quotation," Journal of Combinatorial Optimization, Springer, vol. 27(1), pages 182-198, January.
    11. Chung‐Lun Li & Edward C. Sewell & T. C. E. Cheng, 1995. "Scheduling to minimize release‐time resource consumption and tardiness penalties," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(6), pages 949-966, September.
    12. Cai, X. & Lum, V. Y. S. & Chan, J. M. T., 1997. "Scheduling about a common due date with kob-dependent asymmetric earliness and tardiness penalties," European Journal of Operational Research, Elsevier, vol. 98(1), pages 154-168, April.
    13. Yuan, Jinjiang, 1996. "A note on the complexity of single-machine scheduling with a common due date, earliness-tardiness, and batch delivery costs," European Journal of Operational Research, Elsevier, vol. 94(1), pages 203-205, October.
    14. N. V. R. Mahadev & Aleksandar Pekeč & Fred S. Roberts, 1998. "On the Meaningfulness of Optimal Solutions to Scheduling Problems: Can an Optimal Solution be Nonoptimal?," Operations Research, INFORMS, vol. 46(3-supplem), pages 120-134, June.
    15. Kerem Bülbül & Safia Kedad-Sidhoum & Halil Şen, 2019. "Single-machine common due date total earliness/tardiness scheduling with machine unavailability," Journal of Scheduling, Springer, vol. 22(5), pages 543-565, October.
    16. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    17. Mosheiov, Gur & Shadmon, Michal, 2001. "Minmax earliness-tardiness costs with unit processing time jobs," European Journal of Operational Research, Elsevier, vol. 130(3), pages 638-652, May.
    18. Ramon Alvarez-Valdes & Enric Crespo & Jose Tamarit & Fulgencia Villa, 2012. "Minimizing weighted earliness–tardiness on a single machine with a common due date using quadratic models," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 20(3), pages 754-767, October.
    19. Hendel, Yann & Sourd, Francis, 2006. "Efficient neighborhood search for the one-machine earliness-tardiness scheduling problem," European Journal of Operational Research, Elsevier, vol. 173(1), pages 108-119, August.
    20. Byung-Cheon Choi & Myoung-Ju Park, 2018. "Just-In-Time Scheduling with Generalized Due Dates and Identical Due Date Intervals," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(06), pages 1-13, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:comaot:v:6:y:2000:i:2:d:10.1023_a:1009637419820. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.