| With the progress of the society and the development of economy, machine scheduling problems have more and more applications in our work and life. Machine scheduling has become one of the most important research fields in operations research and combinatorial optimization. Most of the classical scheduling literatures consider the scheduling problems of the jobs coming from a single agent. In practice, the jobs to be scheduled may belong to multiple agents. To attend the distinct requirements of the agents, the decisionmakers need to trade-off the balance between the goals of the agents.The machine scheduling problems with multi-agent can be described as follows. There are k agents and each agent has his respective job set Jx={J1x,…,Jnxx},(1≤x≤k).Moreover,n=Σik=1ni·Pix、dix and wix are the processing time, due date and weight of job Jix, respectively. We have m machines and the agents have to process their jobs on a common processing resource (i.e., the m machines). Each agent wishes to minimize an objective function of his own set of jobs. In this paper, we study the following scheduling problems.In chapter2, we consider two problems on two-agent scheduling on a parallel-batching machine. The first is an unbounded parallel-batching scheduling problem, and the second is a bounded parallel-batching scheduling problem. The objective function of one agent is the makespan of his jobs and the objective function of the other agent is the maximum lateness of his jobs. The problem is to find a schedule that minimizes the linear weighted sum of the objective functions of the two agents. By generating all Pareto optimal points of the two objective functions, we solve the two problems in polynomial times, respectively.In chapter3, we consider the two-agent scheduling problem with rejection on a single machine. In the problem, we have two agents A and B with job families JA and JB, re-spectively. A job of each agent is either accepted and processed on the machine, or rejected with a certain rejection penalty having to be paid. The objective is to minimize the sum of the given objective function fA of the accepted jobs and total rejection penalty of the rejected jobs of the first agent A, given that the sum of the given objective function fB of the accepted jobs and total rejection penalty of the rejected jobs of the agent B does not exceed a fixed value Q (Q>0), where fA and fB are non-decreasing functions on the completion times of their respective jobs. We show that problems are NP-hard for different objective functions. When two agents take the following objectives functions: maximum completion time, the maximum lateness, the total weighted completion time and the total weighted number of late jobs of their jobs, etc., respectively, we provide a pseudo-polynomial-time algorithm. Moreover, when agent A takes the maximum comple-tion time objective, agent B takes the maximum lateness objective and all B-jobs are accepted, we give a pseudo-polynomial-time algorithm, a2-approximation algorithm and a fully polynomial-time approximation scheme (FPTAS), respectively.In chapter4, we consider two-agent scheduling problems on a single machine with maintenance intervals. There are some maintenance intervals in which the machine cannot be available, and the jobs of the two agents have to be processed in the remaining free time-slots. The objective is to minimize the linear combination of the objective functions of the two agents. We analyze the computational complexities of the problems for different objective functions of the two agents:the maximum completion time, the maximum lateness, the total weighted completion time and the total tardiness, etc., and provide polynomial-time algorithms or pseudo-polynomial-time algorithms.In chapter5, we consider three problems on the multi-agent scheduling with earliness cost on a single-machine.In the first problem, we have k=2agents. The processing times of the jobs of the first agent are equal. The due dates of the two agents are equal, too. The objective function of the first agent is the sum of weighted earliness of his jobs. The objective function of the second agent is the maximum earliness of his jobs. The goal of our problem is to minimize the objective function of the first agent given that the objective function of the second does not exceed a fixed value. For the problem, we present a polynomial-time algorithm.In the second problem, we have k agents. The objective functions of the first k-1agents are the maximum earliness of respective jobs. The due dates of the jobs of the k-th agent are equal. The objective function of the k-th agent is the sum of earliness of his jobs. The goal of our problem is to minimize the objective function of the k-th. agent given that the objective functions of the first k-1do not exceed fixed values. For the problem, we present a polynomial time algorithm.In the third problem, we have k=2agents. We assume that each job has a general cost function of his earliness and the cost function is non-decreasing function in earliness of the job. The objective of each agent is the maximum cost function of earliness of his jobs. We analysis the Pareto optimal schedules for the objectives of two agents.In chapter6, we consider an on-line over-list scheduling problem on m(m≥3) iden-tical machines with common maintenance time interval. In scheduling problems with machine availability constraint, if the uncompleted job has to restart from scratch, rather than continue. We call it "nonresumable availability". The objective function is the maximum completion of jobs. For the case that m=2and the length of maintenance time interval is less than or equal to the largest processing time of jobs, we prove that the lower bound of the competitive ratio is2.79129and present an on-line algorithm with the competitive ratio2.79633. For the case thatm≥4and the length of maintenance time interval is larger than the largest processing time of jobs, we prove that any on-line algorithm has not a constant competitive ratio. For the case that the length of mainte-nance time interval is less than or equal to the largest processing time of jobs, there is no on-line algorithm with competitive ratio less than3and give an on-line algorithm with competitive ratio4-m/1. |
PDF Full Text Request