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

Shared multi-processor scheduling

Author

Listed:
  • Dereniowski, Dariusz
  • Kubiak, Wiesław

Abstract

We study shared multi-processor scheduling problem where each job can be executed on its private processor and simultaneously on one of many processors shared by all jobs in order to reduce the job’s completion time due to processing time overlap. The total weighted overlap of all jobs is to be maximized. The problem models subcontracting scheduling in supply chains and divisible load scheduling in computing. We show that synchronized schedules that complete each job at the same time on its private and shared processor, if any is actually used by the job, include optimal schedules. We prove that the problem is NP-hard in the strong sense for jobs with arbitrary weights, and we give an efficient, polynomial-time algorithm for the problem with equal weights.

Suggested Citation

  • Dereniowski, Dariusz & Kubiak, Wiesław, 2017. "Shared multi-processor scheduling," European Journal of Operational Research, Elsevier, vol. 261(2), pages 503-514.
    • Handle: RePEc:eee:ejores:v:261:y:2017:i:2:p:503-514
    DOI: 10.1016/j.ejor.2017.03.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717301819
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.03.002?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. Erol Taymaz & Yilmaz Kilicaslan, 2005. "Determinants of subcontracting and regional development: An empirical study on Turkish textile and engineering industries," Regional Studies, Taylor & Francis Journals, vol. 39(5), pages 633-645.
    2. George L. Vairaktarakis, 2013. "Noncooperative Games for Subcontracting Operations," Manufacturing & Service Operations Management, INFORMS, vol. 15(1), pages 148-158, September.
    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. Dereniowski, Dariusz & Kubiak, Wiesław, 2020. "Shared processor scheduling of multiprocessor jobs," European Journal of Operational Research, Elsevier, vol. 282(2), pages 464-477.
    2. Dariusz Dereniowski & Wiesław Kubiak, 2018. "Shared processor scheduling," Journal of Scheduling, Springer, vol. 21(6), pages 583-593, December.

    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. Anna Giunta & Domenico Scalera & Francesco Trivieri & Jeffrey B. Nugent & Mariarosaria Agostino, 2011. "Firm Productivity, Organizational Choice and Global Value Chain," Working Papers 2011R09, Orkestra - Basque Institute of Competitiveness.
    2. Antonietti, Roberto & Cainelli, Giulio & Lupi, Claudio, 2013. "Vertical disintegration and spatial co-localization: The case of Kibs in the metropolitan region of Milan," Economics Letters, Elsevier, vol. 118(2), pages 360-363.
    3. Dereniowski, Dariusz & Kubiak, Wiesław, 2020. "Shared processor scheduling of multiprocessor jobs," European Journal of Operational Research, Elsevier, vol. 282(2), pages 464-477.
    4. Catherine J. Morrison Paul & Mahmut Yasar, 2009. "Outsourcing, productivity, and input composition at the plant level," Canadian Journal of Economics, Canadian Economics Association, vol. 42(2), pages 422-439, May.
    5. Katarzyna Kowalska, 2016. "Network Organizations And Corporate Social Responsibility," Oeconomia Copernicana, Institute of Economic Research, vol. 7(4), pages 653-668, December.
    6. Roberto Antonietti & Maria Rosaria Ferrante & Riccardo Leoncini, 2016. "Local market size, social capital and outsourcing: evidence from Emilia Romagna," Small Business Economics, Springer, vol. 47(1), pages 243-260, June.
    7. Manuel Artis & Raul Ramos & Jordi Suriñach, 2006. "Job losses, outsourcing and relocation, empirical evidence using microdata," IREA Working Papers 200601, University of Barcelona, Research Institute of Applied Economics, revised Dec 2006.
    8. Davide Antonioli & Massimiliano Mazzanti & Sandro Montresor & Paolo Pini, 2015. "Outsourcing and Firm Productivity in a Specific Local Production System: Evidence from Reggio Emilia (Italy)," Growth and Change, Wiley Blackwell, vol. 46(2), pages 292-320, June.
    9. Herbert Hamers & Flip Klijn & Marco Slikker, 2013. "Price of Anarchy in Sequencing Situations and the Impossibility to Coordinate," Working Papers 709, Barcelona School of Economics.
    10. Charlie Karlsson & Urban Gråsjö & Sofia Wixe (ed.), 2015. "Innovation and Entrepreneurship in the Global Economy," Books, Edward Elgar Publishing, number 15906.
    11. T. Ciarli & R. Leoncini & S. Montresor & M. Valente, 2007. "Organisation of industry and innovation dynamics," Working Papers 609, Dipartimento Scienze Economiche, Universita' di Bologna.
    12. khalifah, noor & Jaafar, Zakiah, 2017. "Technical Efficiency of Establishments in Malaysia’s Electrical and Electronics Industries: Exporting or Vertical Trade?," Jurnal Ekonomi Malaysia, Faculty of Economics and Business, Universiti Kebangsaan Malaysia, vol. 51(1), pages 157-130.
    13. Roberto Antonietti & Maria Rosaria Ferrante & Riccardo Leoncini, 2014. "Trust your neighbour. Industrial relatedness, social capital and outsourcing," Papers in Evolutionary Economic Geography (PEEG) 1403, Utrecht University, Department of Human Geography and Spatial Planning, Group Economic Geography, revised Jan 2014.
    14. Manel Antelo & Lluís Bru, 2018. "Option Contracts in a Vertical Industry," Manchester School, University of Manchester, vol. 86(4), pages 533-557, July.
    15. Kwangho Woo & Joonmo Cho, 2016. "Transferring the Cost of Wage Rigidity to Subcontracting Firms: The Case of Korea," Sustainability, MDPI, vol. 8(9), pages 1-15, August.
    16. Roberto Antonietti & Maria Rosaria Ferrante & Riccardo Leoncini, 2015. "Infrastructure endowment, social capital and outsourcing: evidence from Emilia Romagna, Italy," Chapters, in: Charlie Karlsson & Urban Gråsjö & Sofia Wixe (ed.), Innovation and Entrepreneurship in the Global Economy, chapter 13, pages 310-330, Edward Elgar Publishing.
    17. Holl, Adelheid, 2008. "Production subcontracting and location," Regional Science and Urban Economics, Elsevier, vol. 38(3), pages 299-309, May.
    18. Co, Catherine Y. & Nguyen, Thu Kim & Nguyen, Tung Nhu & Tran, Que Nguyet, 2018. "The exporting and subcontracting decisions of Viet Nam's small- and medium-sized enterprises," International Review of Economics & Finance, Elsevier, vol. 58(C), pages 449-466.
    19. Dipa Mukherjee, 2022. "Subcontracting: A Stepping Stone for Modernisation or a Survival Strategy for Unorganised Manufacturing Sector in India?," The Indian Journal of Labour Economics, Springer;The Indian Society of Labour Economics (ISLE), vol. 65(4), pages 1155-1177, December.
    20. Roberto Antonietti & Giulio Cainelli, 2011. "Geographic concentration and vertical disintegration in KIBS: evidence from the metropolitan area of Milan," Openloc Working Papers 1105, Public policies and local development.

    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:261:y:2017:i:2:p:503-514. 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.