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
Autor: | Vahid Nasrollahi, Mohammad Reisi-Nafchi, Ghasem Moslehi |
---|---|
Rok vydání: | 2020 |
Předmět: |
0209 industrial biotechnology
Numerical Analysis Mathematical optimization 021103 operations research Branch and bound Computer science Strategy and Management Tardiness 0211 other engineering and technologies Scheduling (production processes) Computational intelligence 02 engineering and technology Two agent Flow shop scheduling Management Science and Operations Research Zero (linguistics) 020901 industrial engineering & automation Computational Theory and Mathematics Management of Technology and Innovation Modeling and Simulation Single agent Statistics Probability and Uncertainty |
Zdroj: | Operational Research. 22:1403-1442 |
ISSN: | 1866-1505 1109-2858 |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |