Scheduling problems with two competing agents to minimize minmax and minsum earliness measures

A relatively new class of scheduling problems consists of multiple agents who compete on the use of a common processor. We focus in this paper on a two-agent setting. Each of the agents has a set of jobs to be processed on the same processor, and each of the agents wants to minimize a measure which depends on the completion times of its own jobs. The goal is to schedule the jobs such that the combined schedule performs well with respect to the measures of both agents. We consider measures of minmax and minsum earliness. Specifically, we focus on minimizing maximum earliness cost or total (weighted) earliness cost of one agent, subject to an upper bound on the maximum earliness cost of the other agent. We introduce a polynomial-time solution for the minmax problem, and prove NP-hardness for the weighted minsum case. The unweighted minsum problem is shown to have a polynomial-time solution.     

Polynomial time solutions for scheduling problems on a proportionate flowshop with two competing agents

In scheduling problems with two competing agents, each one of the agents has his own set of jobs and his own objective function, but both share the same processor. The goal is to minimize the value of the objective function of one agent, subject to an upper bound on the value of the objective function of the second agent. In this paper we study two-agent scheduling problems on a proportionate flowshop. Three objective functions of the first agent are considered: minimum maximum cost of all the jobs, minimum total completion time, and minimum number of tardy jobs. For the second agent, an upper bound on the maximum allowable cost is assumed. We introduce efficient polynomial time solution algorithms for all cases.     

Multi-agent single machine scheduling

We consider the scheduling problems arising when several agents, each owning a set of nonpreemptive jobs, compete to perform their respective jobs on one shared processing resource. Each agent wants to minimize a certain cost function, which depends on the completion times of its jobs only. The cost functions we consider in this paper are maximum of regular functions (associated with each job), number of late jobs and total weighted completion time. The different combinations of the cost functions of each agent lead to various problems, whose computational complexity is analysed in this paper. In particular, we investigate the problem of finding schedules whose cost for each agent does not exceed a given bound for each agent.     

Two-agent single-machine scheduling problems under increasing linear deterioration

A new scheduling model in which both two-agent and increasing linear deterioration exist simultaneously is investigated in this paper. The processing time of a job is defined as an increasing linear function of its starting time. Two agents compete to perform their respective jobs on a common single machine and each agent has his own criterion to optimize. We introduce an increasing linear deterioration model into the two-agent single-machine scheduling, where the goal is to minimize the objective function of the first agent with the restriction that the objective function of the second agent cannot exceed a given upper bound. We study two scheduling problems with the different combinations of two agents’ objective functions: makespan, maximum lateness, maximum cost and total completion time. We propose the optimal properties and present the optimal polynomial time algorithms to solve the scheduling problems, respectively.     

有关单机两代理排序问题的两个结果

研究了两个单机两代理排序问题. 在第一个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化最大工件费用. 在第二个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化所有工件的最大完工时间. 证明了第一个问题是强NP-难的, 改进了已有的一般意义NP-难的结果; 对第二个问题给出了一个与现有的动态规划算法不同的动态规划算法.     

Single machine scheduling with a general exponential learning effect

In this paper we consider the scheduling problem with a general exponential learning effect and past-sequence-dependent (p-s-d) setup times. By the general exponential learning effect, we mean that the processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the δ ? 0th power of completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

Coordination mechanisms with hybrid local policies

We study coordination mechanisms for scheduling n jobs on m parallel machines where agents representing the jobs interact to generate a schedule. Each agent acts selfishly to minimize the completion time of his/her own job, without considering the overall system performance that is measured by a central objective. The performance deterioration due to the lack of a central coordination, the so-called price of anarchy, is determined by the maximum ratio of the central objective function value of an equilibrium schedule divided by the optimal value. In the first part of the paper, we consider a mixed local policy with some machines using the SPT rule and other machines using the LPT rule. We obtain the exact price of anarchy for the problem of minimizing the makespan and some bounds for the problem of minimizing the total completion time. In the second part of the paper, we consider parallel machine scheduling subject to eligibility constraints. We devise new local policies based on the flexibilities and the processing times of the jobs. We show that the newly devised local policies outperform both the SPT and the LPT rules.     

A combined approach for two-agent scheduling with sum-of-processing-times-based learning effect

This paper considers a scheduling model involving two agents, job release times, and the sum-of-processing-times-based learning effect. The sum-of-processing-times-based learning effect means that the actual processing time of a job of either agent is a decreasing function of the sum of the processing times of the jobs already scheduled in a given schedule. The goal is to seek for an optimal schedule that minimizes the total weighted completion time of the first agent, subject to no tardy job for the second agent. We first provide a branch-and-bound method to solve the problem. We then develop an approach that combines genetic algorithm and simulated annealing to seek for approximate solutions for the problem. We carry on extensive computational tests to assess the performance of the proposed algorithms.     

Single machine scheduling with general time-dependent deterioration, position-dependent learning and past-sequence-dependent setup times

The paper deals with single machine scheduling problems with setup time considerations where the actual processing time of a job is not only a non-decreasing function of the total normal processing times of the jobs already processed, but also a non-increasing function of the job’s position in the sequence. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). We consider the following objective functions: the makespan, the total completion time, the sum of the δth (δ ≥ 0) power of job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the δ th (δ ≥ 0) power of job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

A single-machine scheduling problem with two-agent and deteriorating jobs

Deteriorating jobs scheduling problems have been extensively studied in recent years. However, it is assumed that there is a common goal to minimize for all jobs in most of the research. In many management situations, multiple agents compete on the usage of a common processing resource. In this paper, we considered a single-machine scheduling problem with a linear deterioration assumption where the objective is to minimize the total weighted completion time of jobs from the first agent with the restriction that no tardy job is allowed for the second agent. We proposed a branch-and-bound algorithm and three heuristic algorithms to search for the optimal solution and near-optimal solutions, respectively. A computational experiment was conducted to evaluate the performance of the proposed algorithms.     

Coordination mechanisms for parallel machine scheduling

We consider coordination mechanisms for the distributed scheduling of n jobs on m parallel machines, where each agent holding a job selects a machine to process his/her own job. Without a central authority to construct a schedule, each agent acts selfishly to minimize his/her own disutility, which is either the completion time of the job or the congestion time (defined as the load of the machine on which the job is scheduled). However, the overall system performance is measured by a central objective which is quite different from the agents’ objective. In the literature, makespan is often considered as the central objective. We, however, investigate problems with other central objectives that minimize the total congestion time, the total completion time, the maximum tardiness, the total tardiness, and the number of tardy jobs. The performance deterioration of the central objective by a lack of central coordination, referred to as the price of anarchy, is typically measured by the maximum ratio of the objective function value of a Nash equilibrium schedule versus that of an optimal, coordinated schedule. In this paper we give bounds for the price of anarchy for the above objectives. For problems with due date related objectives, the price of anarchy may not be defined since the optimal value may be zero. In this case, we consider the maximum difference between the objective function value of an equilibrium schedule and the optimal value. We refer to this metric as the absolute price of anarchy and analyze its lower and upper bounds.     

Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects

In this paper we consider the single machine past-sequence-dependent (p-s-d) setup times scheduling problems with general position-dependent and time-dependent learning effects. By the general position-dependent and time-dependent learning effects, we mean that the actual processing time of a job is not only a function of the total normal processing times of the jobs already processed, but also a function of the job’s scheduled position. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the θth (θ ? 0) power of job completion times, the total lateness, the total weighted completion time, the maximum lateness, the maximum tardiness and the number of tardy jobs. We show that the problems of makespan, the total completion time, the sum of the θth (θ ? 0) power of job completion times and the total lateness can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem, the maximum lateness minimization problem, maximum tardiness minimization problem and the number of tardy jobs minimization problem can be solved in polynomial time under certain conditions.     

Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling

We extend the classical linear assignment problem to the case where the cost of assigning agent j to task i is a multiplication of task i’s cost parameter by a cost function of agent j. The cost function of agent j is a linear function of the amount of resource allocated to the agent. A solution for our assignment problem is defined by the assignment of agents to tasks and by a resource allocation to each agent. The quality of a solution is measured by two criteria. The first criterion is the total assignment cost and the second is the total weighted resource consumption. We address these criteria via four different problem variations. We prove that our assignment problem is NP-hard for three of the four variations, even if all the resource consumption weights are equal. However, and somewhat surprisingly, we find that the fourth variation is solvable in polynomial time. In addition, we find that our assignment problem is equivalent to a large set of important scheduling problems whose complexity has been an open question until now, for three of the four variations.     

Two-agent scheduling with position-based deteriorating jobs and learning effects

Scheduling with deteriorating jobs and learning effects has been widely studied. However, multi-agent scheduling with simultaneous considerations of deteriorating jobs and learning effects has hardly been considered until now. In view of this, we consider a two-agent single-machine scheduling problem involving deteriorating jobs and learning effects simultaneously. In the proposed model, given a schedule, we assume that the actual processing time of a job of the first agent is a function of position-based learning while the actual processing time of a job of the second agent is a function of position-based deterioration. The objective is to minimize the total weighted completion time of the jobs of the first agent with the restriction that no tardy job is allowed for the second agent. We develop a branch-and-bound and several simulated annealing algorithms to solve the problem. Computational results show that the proposed algorithms are efficient in producing near-optimal solutions.     

工件可转包加工的排序问题研究

研究工件可以转包加工的单台机排序问题: 有n个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问题已经被证明是NP-难的. 最后给出该问题的伪多项式时间最优算法, 并且提出一个完全多项式时间近似方案(FPTAS).     

Batch delivery scheduling with batch delivery cost on a single machine

We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on a single machine. The jobs are delivered in batches and the delivery date of a batch equals the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total weighted flow time and delivery cost. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B, the problem remains strongly NP-hard when B ? U for a variable U ? 2 or B ? U for any constant U ? 2. For the case of B ? U, we present a dynamic programming algorithm that runs in pseudo-polynomial time for any constant U ? 2. Furthermore, optimal algorithms are provided for two special cases: (i) jobs have a linear precedence constraint, and (ii) jobs satisfy the agreeable ratio assumption, which is valid, for example, when all the weights or all the processing times are equal.     

Complexity results for the linear time–cost tradeoff problem with multiple milestones and completely ordered jobs

We consider two linear project time–cost tradeoff problems with multiple milestones. Unless a milestone is completed on time, penalty costs for tardiness may be imposed. However, these penalty costs can be avoided by compressing the processing times of certain jobs that require additional resources or costs. Our model describes these penalty costs as the total weighted number of tardy milestone. The first problem tries to minimize the total weighted number of tardy milestones within the budget for total compression costs, while the second problem tries to minimize the total weighted number of tardy milestones plus total compression costs. We develop a linear programming formulation for the case with a fixed number of milestones. For the case with an arbitrary number of milestones, we show that under completely ordered jobs, the first problem is NP-hard in the ordinary sense while the second problem is polynomially solvable.     

A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives

This paper studies the two-agent scheduling on an unbounded parallel-batching machine. In the problem, there are two agents A and B with each having their own job sets. The jobs of a common agent can be processed in a common batch. Moreover, each agent has an objective function to be minimized. The objective function of agent A is the makespan of his jobs and the objective function of agent B is maximum lateness of his jobs. Yazdani Sabouni and Jolai [M.T. Yazdani Sabouni, F. Jolai, Optimal methods for batch processing problem with makespan and maximum lateness objectives, Appl. Math. Model. 34 (2010) 314–324] presented a polynomial-time algorithm for the problem to minimize a positive combination of the two agents’ objective functions. Unfortunately, their algorithm is incorrect. We then dwell on the problem and present a polynomial-time algorithm for finding all Pareto optimal solutions of this two-agent parallel-batching scheduling problem.     

Single-machine scheduling of proportionally deteriorating jobs by two agents

We consider a problem of scheduling a set of independent jobs by two agents on a single machine. Every agent has its own subset of jobs to be scheduled and uses its own optimality criterion. The processing time of each job proportionally deteriorates with respect to the starting time of the job. The problem is to find a schedule that minimizes the total tardiness of the first agent, provided that no tardy job is allowed for the second agent. We prove basic properties of the problem and give a lower bound on the optimal value of the total tardiness criterion. On the basis of these results, we propose a branch-and-bound algorithm and an evolutionary algorithm for the problem. Computational experiments show that the exact algorithm solves instances up to 50 jobs in a reasonably short time and that solutions obtained by the metaheuristic are close to optimal ones.     

Scheduling with target start times

We address the single-machine problem of scheduling n independent jobs subject to target start times. Target start times are essentially release times that may be violated at a certain cost. The objective is to minimize a bicriteria objective function that is composed of total completion time and maximum promptness, which measures the observance of these target start times. We show that in case of a linear objective function the problem is solvable in O(n⁴) time if preemption is allowed or if total completion time outweighs maximum promptness.