Bicriteria fabrication scheduling of two-component jobs on a single machine

Yijie Li ()
Additional contact information
Yijie Li: University of St Andrews

Operational Research, 2023, vol. 23, issue 4, No 3, 13 pages

Abstract: Abstract This paper studies the bicriteria problem of non-preemptively scheduling n jobs, each of which is associated with a due date and comprises a standard and a specific component, on a single fabrication machine to minimize makespan and maximum lateness simultaneously. The specific components are processed individually and the standard components are grouped into batches for processing. A setup time is required before each batch of standard components is processed. A standard component is available (i.e., ready for delivery to the next production stage) only when the batch it belongs to is totally completed, whereas a specific component is available on completion of its processing. The completion time of a job is defined as the moment when both its two components have been processed and are available. An $$O(n^2\log n)$$ O ( n 2 log n ) -time algorithm with linear memory requirements is presented which can generate all Pareto optimal points and find a corresponding Pareto optimal schedule for each Pareto optimal point.

Keywords: Scheduling; Batch processing; Bicriteria optimization; Two-component jobs; Maximum lateness; Single machine; 90B35; 68Q25 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-023-00799-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:23:y:2023:i:4:d:10.1007_s12351-023-00799-1

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-023-00799-1

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().