برنامه ریزی به موقع با دو عامل رقابت در ماشین های موازی نامربوط  Just-in-time scheduling with two competing agents on unrelated parallel machines

1. Introduction In classical just-in-time scheduling, the objective is to minimize the earliness–tardiness cost of completing jobs with respect to their due dates. Most papers in this area consider the objective of minimizing the sum of the earliness and tardiness penalties (see, e.g., [9,24,27,28]). In some situations, the earliness and tardiness penalties depend on whether the jobs are early or tardy, rather than how early or how late they are. Lann and Mosheiov [15] introduce a new objective of minimizing the weighted number of jobs that are early or tardy, which corresponds to maximizing the weighted number of jobs that are completed exactly on their due dates. We refer to any scheduling problem with the objective of maximizing the weighted number of just-in-time jobs as a just-intime scheduling problem. Lann and Mosheiov’s study has recently received growing attention from the scheduling research community and just-intime scheduling has been studied in various machine settings. For the single-machine case, Lann and Mosheiov [15] show that the just-in-time scheduling problem is solvable in Oðn2Þ time, where n is the number of jobs. For the two-machine flowshop case, Choi and Yoon [8] prove that it is NP-hard, but they leave an open question whether the problem is NP-hard in the ordinary sense or in the strong sense. In addition, they show that the unweighted version of the problem can be solved in Oðn4Þ time for the two parallel-machine case and is NP-hard in the strong sense for the three parallel-machine case. Shabtay and Bensoussan [20] show that the open problem left in Choi and Yoon [8] is NP-hard in the ordinary sense by developing a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme (FPTAS) for the problem. Elalouf et al. [10] suggest another pseudopolynomial-time algorithm for the same problem, which can be converted into a new FPTAS that reduces Shabtay and Bensoussan’s complexity result. Shabtay [19] studies the just-in-time problem in the flowshop setting under four different scenarios. For each scenario, he either presents a polynomial-time algorithm or develops an efficient pseudo-polynomial-time algorithm. Shabtay et al. [21] address a two-machine flowshop scheduling problem where the job processing time is controllable by varying the allocation of a resource to the job operations. They adopt a bicriterion analysis of the problem in which the first objective is to maximize the weighted number of just-in-time jobs while the second objective is to minimize the total resource consumption cost. They develop a pseudo-polynomial-time algorithm for the problem and convert it into a two-dimensional FPTAS. In the parallel-machine setting, Carlisle and Lloyd [6] consider the unweighted version of the just-in-time scheduling problem on m identical parallel machines and show that the problem can be solved in Oðn log nÞ time. Other solution algorithms for the same problem can be found in C̆ epek and Sung [7], Frank [11], Yannakakis and Gavril [26], and Hsiao et al. [13]. Arkin and Silverberg [2] develop an Oðn2 log nÞ time solution algorithm for the weighted case on m identical parallel machines by converting the problem into a minimum cost flow problem. Bouzina and Emmonss [5], and Carlisle and Lloyd [6] present more efficient minimum cost flow algorithms with an Oðmn log nÞ running time for the same problem by modelling it on a network that has only O(n) arcs. Kovalyov et al. [14] show that the just-in-time scheduling problem on unrelated parallel machines is equivalent to that of maximizing the weighted m legally colourable vertices in a given interval graph. Both Arkin and Silverberg [2], and Sung and Vlach [23] prove that the just-in-time scheduling problem on m unrelated parallel machines can be solved in Oðmnm þ1Þ time, which is polynomial when m is fixed. However, when m is arbitrary, they show that the problem becomes NP-hard in the strong sense. Leyvand et al. [16] consider just-in-time scheduling on a set of m machines with controllable processing times, where the objectives are to maximize the weighted number of just-in-time jobs and to minimize the total resource allocation cost. They consider four different models for treating the two criteria. For each model, they either provide a polynomial-time solution algorithm or develop a pseudo-polynomial-time solution algorithm and an FPTAS. All the above papers focus on the traditional case of just-in-time scheduling with a single agent. In recent years researchers have increasingly considered scheduling with multiple competing agents, which was initially investigated by Agnetis et al. [1] and Baker and Smith [3]. In this case, multiple agents need to process their own sets of jobs, competing for the use of a common resource. Each agent wants to optimize a certain objective function, which depends on the completion times of its jobs only. Variants of the scheduling problem with multiple agents have found many applications in areas such as manufacturing, supply chain management, telecommunication services, project scheduling, etc. A recent survey of multi-agent scheduling research is given in Perez–Gonzalez and Framinan [17]. With a view to modelling a realistic production system, this paper combines the two sub-fields into a unified framework. Specifically, we focus on the innovative just-in-time scheduling model on unrelated parallel machines in the twoagent setting. The purpose of this paper is twofold. One is to investigate this unexplored scheduling model. Another is to ascertain the computational complexity status and provide solution procedures, if viable, for the problems under consideration.