Algorithms for a two-machine no-wait flow shop scheduling problem with two competing agents

期刊论文
发表日期：

2024年7月30日

查看全文

Qi-Xia Yang,
Long-Cheng Liu,
Min Huang,
Tian-Run Wang

摘要

In this paper, we consider the following two-machine no-wait flow shop scheduling problem with two competing agents $F2~|~M_1\rightarrow M_2,~ M_2,~ p_{ij}^{A} = p,~ no\text{- }wait~|~C_{\max }^A:~ C_{\max }^B~\le Q $ $F 2 | M_{1} \to M_{2}, M_{2}, p_{ij}^{A} = p, n o - w a i t | C_{max}^{A} : C_{max}^{B} \leq Q$ : Given a set of n jobs $\mathcal {J} = \{ J_1, J_2, \ldots , J_n\}$ $J = {J_{1}, J_{2}, \dots, J_{n}}$ and two competing agents A and B. Agent A is associated with a set of $n_A$ $n_{A}$ jobs $\mathcal {J}^A = \{J_1^A, J_2^A, \ldots , J_{n_A}^A\}$ $J^{A} = {J_{1}^{A}, J_{2}^{A}, \dots, J_{n_{A}}^{A}}$ to be processed on the machine $M_1$ $M_{1}$ first and then on the machine $M_2$ $M_{2}$ with no-wait constraint, and agent B is associated with a set of $n_B$ $n_{B}$ jobs $\mathcal {J}^B = \{J_1^B, J_2^B, \ldots , J_{n_B}^B\}$ $J^{B} = {J_{1}^{B}, J_{2}^{B}, \dots, J_{n_{B}}^{B}}$ to be processed on the machine $M_2$ $M_{2}$ only, where the processing times for the jobs of agent A are all the same (i.e., $p_{ij}^A = p$ $p_{ij}^{A} = p$ ), $\mathcal {J} = \mathcal {J}^A \cup \mathcal {J}^B$ $J = J^{A} \cup J^{B}$ and $n = n_A + n_B$ $n = n_{A} + n_{B}$ . The objective is to build a schedule $\pi $ $π$ of the n jobs that minimizing the makespan of agent A while maintaining the makespan of agent B not greater than a given value Q. We first show that the problem is polynomial time solvable in some special cases. For the non-solvable case, we present an $O(n \log n)$ $O (n log n)$ -time $(1 + \frac{1}{n_A +1})$ $(1 + \frac{1}{n_{A} + 1})$ -approximation algorithm and show that this ratio of $(1 + \frac{1}{n_A +1})$ $(1 + \frac{1}{n_{A} + 1})$ is asymptotically tight. Finally, $(1+\epsilon )$ $(1 + ϵ)$ -approximation algorithms are provided.