IDEAS home Printed from https://ideas.repec.org/a/taf/tprsxx/v56y2018i3p1030-1053.html
   My bibliography  Save this article

A bi-objective parallel machine problem with eligibility, release dates and delivery times of the jobs

Author

Listed:
  • Manuel Mateo
  • Jacques Teghem
  • Daniel Tuyttens

Abstract

The scheduling of parallel machines is a well-known problem in many companies. Nevertheless, not always all the jobs can be manufactured in any machine and the eligibility appears. Based on a real-life problem, we present a model which has m parallel machines with different level of quality from the highest level for the first machine till the lowest level for the last machine. The set of jobs to be scheduled on these m parallel machines are also distributed among these m levels: one job from a level can be manufactured in a machine of the same or higher level but a penalty, depending on the level, appears when a job is manufactured in a machine different from the highest level i.e. different from the first machine. Besides, there are release dates and delivery times associated to each job. The tackled problem is bi-objective with the criteria: minimisation of the final date – i.e. the maximum for all the jobs of their completion time plus the delivery time – and the minimisation of the total penalty generated by the jobs. In a first step, we analyse the sub-problem of minimisation of the final date on a single machine for jobs with release dates and delivery times. Four heuristics and an improvement algorithm are proposed and compared on didactic examples and on a large set of instances. In a second step an algorithm is proposed to approximate the set of efficient solutions and the Pareto front of the bi-objective problem. This algorithm contains two phases: the first is a depth search phase and the second is a backtracking phase. The procedure is illustrated in detail on an instance with 20 jobs and 3 machines. Then extensive numerical experiments are realised on two different sets of instances, with 20, 30 and 50 jobs, 3 or 4 machines and various values of penalties. Except for the case of 50 jobs, the results are compared with the exact Pareto front.

Suggested Citation

  • Manuel Mateo & Jacques Teghem & Daniel Tuyttens, 2018. "A bi-objective parallel machine problem with eligibility, release dates and delivery times of the jobs," International Journal of Production Research, Taylor & Francis Journals, vol. 56(3), pages 1030-1053, February.
    • Handle: RePEc:taf:tprsxx:v:56:y:2018:i:3:p:1030-1053
    DOI: 10.1080/00207543.2017.1351634
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/00207543.2017.1351634
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1080/00207543.2017.1351634?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.

    Citations

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


    Cited by:

    1. Söhnke Maecker & Liji Shen, 2020. "Solving parallel machine problems with delivery times and tardiness objectives," Annals of Operations Research, Springer, vol. 285(1), pages 315-334, February.
    2. Yang-Kuei Lin & Tzu-Yueh Yin, 2022. "Generating bicriteria schedules for correlated parallel machines involving tardy jobs and weighted completion time," Annals of Operations Research, Springer, vol. 319(2), pages 1655-1688, December.
    3. Hongyu He & Yanzhi Zhao & Xiaojun Ma & Yuan-Yuan Lu & Na Ren & Ji-Bo Wang, 2023. "Study on Scheduling Problems with Learning Effects and Past Sequence Delivery Times," Mathematics, MDPI, vol. 11(19), pages 1-19, September.

    More about this item

    Statistics

    Access and download statistics

    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:taf:tprsxx:v:56:y:2018:i:3:p:1030-1053. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Longhurst (email available below). General contact details of provider: http://www.tandfonline.com/TPRS20 .

    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.