IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v205y2010i3p528-539.html
   My bibliography  Save this article

Scheduling two agents with controllable processing times

Author

Listed:
  • Wan, Guohua
  • Vakati, Sudheer R.
  • Leung, Joseph Y.-T.
  • Pinedo, Michael

Abstract

We consider several two-agent scheduling problems with controllable job processing times, where agents A and B have to share either a single machine or two identical machines in parallel while processing their jobs. The processing times of the jobs of agent A are compressible at additional cost. The objective function for agent B is always the same, namely a regular function fmax. Several different objective functions are considered for agent A, including the total completion time plus compression cost, the maximum tardiness plus compression cost, the maximum lateness plus compression cost and the total compression cost subject to deadline constraints (the imprecise computation model). All problems are to minimize the objective function of agent A subject to a given upper bound on the objective function of agent B. These problems have various applications in computer systems as well as in operations management. We provide NP-hardness proofs for the more general problems and polynomial-time algorithms for several special cases of the problems.

Suggested Citation

  • Wan, Guohua & Vakati, Sudheer R. & Leung, Joseph Y.-T. & Pinedo, Michael, 2010. "Scheduling two agents with controllable processing times," European Journal of Operational Research, Elsevier, vol. 205(3), pages 528-539, September.
    • Handle: RePEc:eee:ejores:v:205:y:2010:i:3:p:528-539
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00013-5
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Van Wassenhove, Luk N. & Baker, Kenneth R., 1982. "A bicriterion approach to time/cost trade-offs in sequencing," European Journal of Operational Research, Elsevier, vol. 11(1), pages 48-54, September.
    2. Cheng, T.C.E. & Ng, C.T. & Yuan, J.J., 2008. "Multi-agent scheduling on a single machine with max-form criteria," European Journal of Operational Research, Elsevier, vol. 188(2), pages 603-609, July.
    3. Janiak, Adam & Kovalyov, Mikhail Y., 1996. "Single machine scheduling subject to deadlines and resource dependent processing times," European Journal of Operational Research, Elsevier, vol. 94(2), pages 284-291, October.
    4. Joseph Y.-T. Leung & Michael Pinedo & Guohua Wan, 2010. "Competitive Two-Agent Scheduling and Its Applications," Operations Research, INFORMS, vol. 58(2), pages 458-469, April.
    5. C. N. Potts & L. N. Van Wassenhove, 1992. "Single Machine Scheduling to Minimize Total Late Work," Operations Research, INFORMS, vol. 40(3), pages 586-595, June.
    6. Janiak, Adam, 1998. "Minimization of the makespan in a two-machine problem under given resource constraints," European Journal of Operational Research, Elsevier, vol. 107(2), pages 325-337, June.
    7. Janiak, Adam & Kovalyov, Mikhail Y. & Kubiak, Wieslaw & Werner, Frank, 2005. "Positive half-products and scheduling with controllable processing times," European Journal of Operational Research, Elsevier, vol. 165(2), pages 416-422, September.
    8. Allesandro Agnetis & Pitu B. Mirchandani & Dario Pacciarelli & Andrea Pacifici, 2004. "Scheduling Problems with Two Competing Agents," Operations Research, INFORMS, vol. 52(2), pages 229-242, April.
    9. R. G. Vickson, 1980. "Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine," Operations Research, INFORMS, vol. 28(5), pages 1155-1167, October.
    10. Robert McNaughton, 1959. "Scheduling with Deadlines and Loss Functions," Management Science, INFORMS, vol. 6(1), pages 1-12, October.
    11. Grabowski, Jozef & Janiak, Adam, 1987. "Job-shop scheduling with resource-time models of operations," European Journal of Operational Research, Elsevier, vol. 28(1), pages 58-73, January.
    12. Cheng, T. C. Edwin & Janiak, Adam & Kovalyov, Mikhail Y., 2001. "Single machine batch scheduling with resource dependent setup and processing times," European Journal of Operational Research, Elsevier, vol. 135(1), pages 177-183, November.
    Full references (including those not matched with items on IDEAS)

    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. Ruyan He & Jinjiang Yuan, 2020. "Two-Agent Preemptive Pareto-Scheduling to Minimize Late Work and Other Criteria," Mathematics, MDPI, vol. 8(9), pages 1-18, September.
    2. Shabtay, Dvir & Kaspi, Moshe, 2006. "Parallel machine scheduling with a convex resource consumption function," European Journal of Operational Research, Elsevier, vol. 173(1), pages 92-107, August.
    3. Carrasco, Rodrigo A. & Iyengar, Garud & Stein, Cliff, 2018. "Resource cost aware scheduling," European Journal of Operational Research, Elsevier, vol. 269(2), pages 621-632.
    4. Yaron Leyvand & Dvir Shabtay & George Steiner & Liron Yedidsion, 2010. "Just-in-time scheduling with controllable processing times on parallel machines," Journal of Combinatorial Optimization, Springer, vol. 19(3), pages 347-368, April.
    5. Choi, Byung-Cheon & Yoon, Suk-Hun & Chung, Sung-Jin, 2007. "Single machine scheduling problem with controllable processing times and resource dependent release times," European Journal of Operational Research, Elsevier, vol. 181(2), pages 645-653, September.
    6. Liu Guiqing & Li Kai & Cheng Bayi, 2015. "Preemptive Scheduling with Controllable Processing Times on Parallel Machines," Journal of Systems Science and Information, De Gruyter, vol. 3(1), pages 68-76, February.
    7. Nong, Q.Q. & Cheng, T.C.E. & Ng, C.T., 2011. "Two-agent scheduling to minimize the total cost," European Journal of Operational Research, Elsevier, vol. 215(1), pages 39-44, November.
    8. Ren-Xia Chen & Shi-Sheng Li, 2019. "Two-agent single-machine scheduling with cumulative deterioration," 4OR, Springer, vol. 17(2), pages 201-219, June.
    9. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.
    10. Xiaoqiang Cai & George L. Vairaktarakis, 2012. "Coordination of Outsourced Operations at a Third-Party Facility Subject to Booking, Overtime, and Tardiness Costs," Operations Research, INFORMS, vol. 60(6), pages 1436-1450, December.
    11. Jun Pei & Jinling Wei & Baoyu Liao & Xinbao Liu & Panos M. Pardalos, 2020. "Two-agent scheduling on bounded parallel-batching machines with an aging effect of job-position-dependent," Annals of Operations Research, Springer, vol. 294(1), pages 191-223, November.
    12. Shabtay, Dvir & Bensoussan, Yaron & Kaspi, Moshe, 2012. "A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system," International Journal of Production Economics, Elsevier, vol. 136(1), pages 67-74.
    13. Hoogeveen, Han, 2005. "Multicriteria scheduling," European Journal of Operational Research, Elsevier, vol. 167(3), pages 592-623, December.
    14. 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.
    15. Zhang Xingong & Wang Yong, 2017. "Two-agent scheduling problems on a single-machine to minimize the total weighted late work," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 945-955, April.
    16. Shi-Sheng Li & Ren-Xia Chen & Qi Feng, 2016. "Scheduling two job families on a single machine with two competitive agents," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 784-799, October.
    17. Du-Juan Wang & Yunqiang Yin & Shuenn-Ren Cheng & T.C.E. Cheng & Chin-Chia Wu, 2016. "Due date assignment and scheduling on a single machine with two competing agents," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 1152-1169, February.
    18. Yuan Zhang & Jinjiang Yuan, 2019. "A note on a two-agent scheduling problem related to the total weighted late work," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 989-999, April.
    19. Wenchang Luo & Lin Chen & Guochuan Zhang, 2012. "Approximation schemes for two-machine flow shop scheduling with two agents," Journal of Combinatorial Optimization, Springer, vol. 24(3), pages 229-239, October.
    20. Phosavanh, Johnson & Oron, Daniel, 2024. "Two-agent single-machine scheduling with a rate-modifying activity," European Journal of Operational Research, Elsevier, vol. 312(3), pages 866-876.

    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:eee:ejores:v:205:y:2010:i:3:p:528-539. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.