Minimizing the weighted sum of maximum earliness and maximum tardiness in a single-agent and two-agent form of a two-machine flow shop scheduling problem

Vahid Nasrollahi (), Ghasem Moslehi () and Mohammad Reisi-Nafchi ()
Additional contact information
Vahid Nasrollahi: Isfahan University of Technology
Ghasem Moslehi: Isfahan University of Technology
Mohammad Reisi-Nafchi: Isfahan University of Technology

Operational Research, 2022, vol. 22, issue 2, No 20, 1403-1442

Abstract: Abstract In the past decade, multi-agent scheduling studies have become more widespread. However, the evaluation of these issues in the flow shop scheduling environment has received almost no attention. In this article, we investigate two problems. One problem is a common due date problem of constrained two-agent scheduling of jobs in a two-machine flow shop environment to minimize the weighted sum of maximum earliness and maximum tardiness of first-agent jobs and restrictions of non-eligibility on the tardiness of second-agent jobs. Another problem is a single-agent form of the two-agent problem when the number of second-agent jobs is zero. So, an optimal algorithm with polynomial time complexity is presented for the single-agent problem. For the two-agent problem, after it was shown to have minimum complexity of ordinary NP-hardness, a branch and bound algorithm, based on efficient lower and upper bounds and dominance rules, was developed. The computational results show that the algorithm can solve the large-size instances optimally.

Keywords: Maximum earliness; Maximum tardiness; Two-agent scheduling; Number of tardy jobs; Flow shop (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s12351-020-00577-3 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:22:y:2022:i:2:d:10.1007_s12351-020-00577-3

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

DOI: 10.1007/s12351-020-00577-3

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 ().