دانلود رایگان مقاله برنامه ریزی به موقع با دو عامل رقابت در ماشین های موازی نامربوط

abstract

This paper considers two-agent just-in-time scheduling where agents A and B have to share m unrelated parallel machines for processing their jobs. The objective of agent A is to maximize the weighted number of its just-in-time jobs that are completed exactly on their due dates, while the objective of agent B is either to maximize its maximum gain (income) from its just-in-time jobs or to maximize the weighted number of its just-in-time jobs. We provide a bicriterion analysis of the problem, which seek to find the Pareto-optimal solutions for each combination of the two agents' criteria. When the number of machines is part of the problem instance, both the addressed problems are NP-hard in the strong sense. When the number of machines is fixed, we show that the problem of maximizing agent A's weighted number of just-in-time jobs while maximizing agent B's maximum gain can be solved in polynomial time, whereas the problem of maximizing both agents' weighted numbers of just-in-time jobs is NP-hard. For the latter problem, we also provide a pseudo-polynomial-time solution algorithm, establishing that it is NP-hard in the ordinary sense, and show that it admits a fully polynomial-time approximation scheme (FPTAS) for finding an approximate Pareto solution.

5. Concluding remarks

In this paper we consider the just-in-time scheduling involving two agents that compete for the usage of m unrelated parallel machines, where one agent wants to maximize the weighted number of its just-in-time jobs, while the other agent wants to maximize its maximum gain or to maximize the weighted number of its just-intime jobs. The goal is to find Pareto-optimal solutions for each combination of the two agents' criteria. When the number of machines is part of the problem instance, both the addressed problems are NPhard in the strong sense. When the number of machines is fixed, we show that the RmjjðP J A k AEAwA k ; maxJ B k AEBwB k Þ problem can be solved in Oðm2nm þ1 A nBÞ time, while the RmjjðP J A k AEAwA k ; P J B k AEBwB k Þ problem is NP-hard. For the latter problem, we present a pseudopolynomial-time algorithm that runs in Oðm2nm þ1 minfWA; WBgÞ time, implying that the problem is NP-hard in the ordinary sense, and then convert the algorithm into an FPTAS for finding a Pareto optimal solution.