【作者】 丁国生；

【导师】 孙世杰；

【作者基本信息】 上海大学 ， 运筹学与控制论， 2009， 博士

【摘要】 本文主要研究了有多个代理(客户)的排序问题。在这样的问题中,存在着多个代理,每个代理拥有一个特定的工件集合。所有代理的工件都需要在相同的机器上被加工。每个代理的目标函数往往不同,且仅仅依赖于其自身工件的完工时间。我们的任务分三个方面：1)取各个代理目标函数的加权和作为一个总的目标函数,寻找使得总目标函数达到最小的工件序；2)在其它代理的目标函数值受限的条件下,寻找使得某个代理的目标函数达到最小的工件序；3)找到所有的非支配(nondominated)工件序,供决策者权衡各代理之间的利益得失以选择一个可以接受的序。这里的非支配序是指这样的一个序,若改变它使得一个或多个代理的目标函数值比现在小,那么改变以后的序中,必有其他一个或多个代理的目标函数值比现在大。本文第二章介绍了一个特殊的多代理问题：订单问题。订单问题中,每个订单是一个代理,m份订单共有n个工件需要在同一台机器上加工,这n个工件分属k个不同的类,当机器从加工某一类中的工件转向加工不同于它的第j类工件时,需要一个安装时间sj。问题是寻找一个使得m份订单的完工时间之和最小的加工顺序。这一章中,根据安装时间,订单完工的定义的不同,分了三种情形,分别给出了多项式时间算法,分支定界算法和一个启发式算法。第三章就离线和在线模式考虑了一个两代理单机排序问题。两个代理各有一个集合的独立的工件,在不同的时刻到达,或可中断,或不可中断,需要在同一台机器加工。两个代理都不同程度地希望尽早完工,取他们时间表长的加权和为考虑的目标函数。在离线模式下,工件可中断时有最优解；在线模式中,工件可中断时给出了一个竞争比为1+1/θ最优在线算法,不可中断时给出一个2+1/θ的在线算法。第四章又考虑了一个带类安装时间的问题,共两个代理,每个代理的目标均是最小化其时间表长。问题分成两种形式：第一种是求解限制最优问题,即在一个代理的时间表长受限的条件下寻找使得另一代理的时间表长最小的加工顺序,这个问题等价于我们定义的一个有尾巴的背包问题；第二种形式是研究其所有非支配序的数目和特征。第五章考虑了工件加工时间退化的两代理排序问题。工件的加工时间pj=bjt,t≥to,其中bj是工件j的退化率,t,to分别是工件j的开始加工时间和到达时间。考虑的目标有时间表长,总完工时间和最大延迟。每个代理任取一个作为其评价标准,取两个代理的评价标准的加权组合作为问题的目标函数。第五章就这样的六个组合分别给出了多项式算法。第六章考虑了这样的排序问题：有n个工件在同一时刻同时到达同一机器等待被加工,也希望在同一时刻完成加工。如某工件不能如期完工而延误了该工件的下道加_工,则货主会向加工方索取赔偿；反之,如工件提前完工而使该工件可提前下道加工,则货主会给予加工方一定的奖励。因此,对加工方来说要降低成本需考虑一延误惩罚、超前有奖类目标函数,可记之为∑j=1n(αjTj-βjEj)。以此作为目标函数,考虑了工件加工时间同其开始加工时间有关且工件可拒加工的两个排序问题。对这两个排序问题,在指出它们的NP-hard性后,对它们作了详细分析并给出了相应算法。更多还原

【Abstract】 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.更多还原