A Study Of Scheduling Problems With Multiple Competing Agents

This thesis mainly deals with some multi-agent scheduling problems in which each agent is responsible for his own set of jobs and they compete to perform their respective jobs on a common processing resource. Each agent want to minimize a certain objective function, which depends on the completion times of his jobs only. Our goal is to 1) find the optimal schedule when the criteria considered is linear combination of the objective function with weights on each agents; 2) find the optimal schedule for one agent with a constraint on the other agents' objective function; 3) find single nondominated schedules (i.e., such that a better schedule for one or many agents necessarily results in a worse schedule for the other agents), and generating all nondominated schedules.The second chapter in the thesis consider a special multi-agent problem, the scheduling problem with customer orders, in which a customer order is in fact an agent. In this scheduling problem with customer orders, n jobs coming from m different orders need to be processed in the same machine, and these jobs belong to k different families. A setup time Sj is needed before the machine processes a job coming from family j while the just finished job belongs to a different family. The goal is minimize the combination of completion of these m orders. Corresponding to three different models of this scheduling problem, we give a polynomial algorithm, a branch and bound algorithm and a heuristic algorithms, respectively.The third chapter considers the single-machine scheduling problems in which two agents are concerned. Take the makespan of each agent as his own criterion and take the linear combination of the two makespans as objective function. Both off-line and on-line models are considered. When preemption is allowed, we present an exact algorithm for the off-line model and an optimal algorithm for the on-line model. When preemption is not allowed we point out that the problem is NP-hard for the off-line model and give a (2+1/?)-competitive algorithm for the on-line model. We also prove that a lower bound of the competitive ratio for the later model is 1+?/(1+?), where?is a given factor not less than 1The fourth chapter considers two-agent scheduling on a single machine, where there are job families and setup requirements exist between these fami-lies. Each agent's objective function is to minimize his own makespan. One of our goals is to find the optimal solution for one agent with a constraint on the other agent's makespan (constrained optimization). This problem is equivalent to the caudate Knapsack problem that we define in the paper. The other goal is to find single nondominated schedules and to generate all nondominated sched-ules. Finally, two special cases, one with equal job processing times and the other with equal family setups are studied. We prove that the constrained optimization problems in both cases can be solved in polynomial time and that the cases have a polynomial number of nondominated schedules.The fifth chapter considers the scheduling problem involving a single pro-cessor being utilized by two customers with linear deteriorating jobs, i.e. jobs whose processing times are an increasing function of their starting times. We examine the implications of minimizing an aggregate scheduling objective func-tion in which jobs belonging to different customers are evaluated based on their individual criteria. We examine three basic scheduling criteria:minimizing makespan, minimizing total completion time, and minimizing maximum late-ness. We demonstrate that all the scheduling problems considered by us are polynomially solvable.The sixth chapter considers the following scheduling problem:n jobs reach the same machine at the same time to be processed, and also hope to be finished at the same time?The machine can process one job at any time, and any job needs to be processed continuously without interruption. If a job couldn't be finished its processed before or at its due date, the job-owner will ask the factory (machine-owner) pay the penalty; otherwise, the job-owner will pay prize to the factory. Therefore, the factory has to schedule the processing sequence of these n jobs such that the cost is minimized. Taking this as our part objective function, we consider two scheduling problems with learning (deteriorating) jobs and rejection. We prove that both of them are NP-hard, analysis their sub-cases in detail and construct corresponding algorithms for them.