We study the shared processor scheduling problem with a single shared processor where a unit time saving (weight) obtained by processing a job on the shared processor depends on the job. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an @math optimization algorithm for a class of instances in which non-decreasing order of jobs with respect to processing times provides a non-increasing order with respect to weights --- this instance generalizes the unweighted case of the problem. This algorithm also leads to a @math -approximation algorithm for the general weighted problem. The complexity of the weighted problem remains open.
We also remark multi-agent scheduling models in which each agent has its own optimality criterion and performs actions aimed at optimizing it. In these models, being examples of decentralized systems, agents usually have a number of non-divisible jobs to execute (depending on the optimization criterion this may be seen as having one divisible job, but restricted by allowing preemptions only at certain specified points). For minimization of weighted total completion time in such models see Lee et. al. @cite_0 and weighted number of tardy jobs see Cheng, Ng and Yuan @cite_2 . Bukchin and Hanany @cite_6 give an example of a game-theoretic analysis to a problem of this type. For overviews and further references on the multi-agent scheduling we refer to the book by Agnetis et. al. @cite_8 .
@cite_0 @cite_8 @cite_6 @cite_2
2091376812 2463480808 2106447860 1997032351
We consider a multi-agent scheduling problem on a single machine in which each agent is responsible for his own set of jobs and wishes to minimize the total weighted completion time of his own set of jobs. It is known that the unweighted problem with two agents is NP-hard in the ordinary sense. For this case, we can reduce our problem to a Multi-Objective Shortest-Path (MOSP) problem and this reduction leads to several results including Fully Polynomial Time Approximation Schemes (FPTAS). We also provide an efficient approximation algorithm with a reasonably good worst-case ratio. Scheduling theory has received a growing interest since its origins in the second half of the 20th century. Developed initially for the study of scheduling problems with a single objective, the theory has been recently extended to problems involving multiple criteria. However, this extension has still left a gap between the classical multi-criteria approaches and some real-life problems in which not all jobs contribute to the evaluation of each criterion. In this book, we close this gap by presenting and developing multi-agent scheduling models in which subsets of jobs sharing the same resources are evaluated by different criteria. Several scenarios are introduced, depending on the definition and the intersection structure of the job subsets. Complexity results, approximation schemes, heuristics and exact algorithms are discussed for single-machine and parallel-machine scheduling environments. Definitions and algorithms are illustrated with the help of examples and figures. Decentralized organizations may incur inefficiencies because of scheduling issues associated with competition among decision makers (DMs) for limited resources. We analyze the decentralization cost (DC), i.e., the ratio between the Nash equilibrium cost and the cost attained at the centralized optimum. Solution properties of a dispatching-sequencing model are derived and subsequently used to develop bounds on the DC for an arbitrary number of jobs and DMs. A scheduling-based coordinating mechanism is then provided, ensuring that the centralized solution is obtained at equilibrium. We consider the feasibility model of multi-agent scheduling on a single machine, where each agent's objective function is to minimize the total weighted number of tardy jobs. We show that the problem is strongly NP-complete in general. When the number of agents is fixed, we first show that the problem can be solved in pseudo-polynomial time for integral weights, and can be solved in polynomial time for unit weights; then we present a fully polynomial-time approximation scheme for the problem.