Scheduling two job families on a single machine with two competitive agents

We consider the scheduling problems arising when two agents, each with a family of jobs, compete to perform their respective jobs on a single machine. A setup time is needed for a job if it is the first job to be processed on the machine or its processing on the machine follows a job that belongs to another family. Each agent wants to minimize a certain cost function, which depends on the completion times of its jobs only. The aim is to find a schedule for all the jobs of the two agents that minimizes the objective of one agent while keeping the objective of the other agent being bounded by a fixed value \(Q\). Polynomial-time and pseudo-polynomial-time algorithms are designed to solve the problem involving various combinations of regular scheduling objective functions.     

Two-agent scheduling problems on a single-machine to minimize the total weighted late work

In this paper, two-agent scheduling problems are presented. The different agents share a common processing resource, and each agent wants to minimize a cost function depending on its jobs only. The objective functions we consider are the total weighted late work and the maximum cost. The problem is to find a schedule that minimizes the objective function of agent A, while keeping the objective function of agent B cannot exceed a given bound U. Some different scenarios are presented by depending on the objective function of each agent. We address the complexity of those problems, and present the optimal polynomial time algorithms or pseudo-polynomial time algorithm to solve the scheduling problems, respectively.     

Multi-agent scheduling on a single machine with a fixed number of competing agents to minimize the weighted sum of number of tardy jobs and makespans

We study the multi-agent scheduling on a single machine with a fixed number of competing agents, in which, the objective function of each agent is either the number of tardy jobs or the makespan, and the goal of the problem is to minimize the weighted sum of agents’ objective functions. In the literature, the computational complexity of this problem was posed as open. By using enumerating, dynamic programming, and schedule-configuration, we show in this paper that the problem is solvable in polynomial time.     

A Cooperative Savings Game Approach to a Time Sensitive Capacity Allocation and Scheduling Problem

We consider a competitive scheduling setting with arbitrary number of agents each having the option to utilize two parallel resources to satisfy its demand: (i) an in‐house resource dedicated to process only the tasks of each specific agent, and (ii) a flexible resource capable of processing all agents' workloads. In a noncooperative setting, each agent would determine how much of its demand it will subcontract to the flexible resource with the objective to deliver its entire demand as quickly as possible subject to the priority rules set by the owner of the flexible resource (i.e., third‐party). In this study, we also allow for agents to coalesce with other agents and update their initial subcontracting decisions to attain rescheduling savings. Evidently, a grand coalition of all agents can coordinate to achieve the maximum savings possible, but the resulting schedule may yield individual losses for a subset of agents (which we refer to as “losers”), thus necessitating a transfer payment scheme to distribute the rescheduling savings among the agents in an equitable way. We model the rescheduling interactions among the agents as a cooperative savings game, and propose savings distribution schemes that invoke the core allocation concept.     

基于混合流水作业组织的集装箱码头装卸作业集成调度优化

集装箱码头集疏运资源调度的对象是由岸桥、集卡、场桥所构成的多阶段一体化的集装箱装、卸、运操作系统,将该系统的调度优化基于多阶段混合流水线调度问题建立混合整数规划模型,同时考虑集装箱码头现实作业中预定义顺序、避免岸桥交叉作业、以及取决于作业顺序的切换时间等现实约束,针对问题自身的特点设计了两阶段启发式算法,得出各阶段设备的指派结果及作业顺序。通过与基于现行调度规则的调度方案以及与目标函数理论下界值的对比实验,显示了所提出的集成调度模型及求解算法能够有效降低船舶在港时间并实现集卡资源的共享,为集装箱码头集疏运资源的集成调度提供了新的思路。     

Minmax common flow-allowance problems with convex resource allocation and position-dependent workloads

We study minmax due-date based on common flow-allowance assignment and scheduling problems on a single machine, and extend known results in scheduling theory by considering convex resource allocation. The total cost function of a given job consists of its earliness, tardiness and flow-allowance cost components. Thus, the common flow-allowance and the actual jobs’ processing times are decision variables, implying that the due-dates and actual processing times can be controlled by allocating additional resource to the job operations. Consequently, our goal is to optimize a cost function by seeking the optimal job sequence, the optimal job-dependent due-dates along with the actual processing times. In all addressed problems we aim to minimize the maximal cost among all the jobs subject to a constraint on the resource consumption. We start by analyzing and solving the problem with position-independent workloads and then proceed to position-dependent workloads. Finally, the results are generalized to the method of common due-window. For all studied problems closed form solutions are provided, leading to polynomial time solutions.

     

A survey of scheduling problems with late work criteria

The paper presents the first complete survey of scheduling problems with the late work criteria. Late work objective functions estimate the quality of a schedule based on durations of late parts of jobs, not taking into account the amount of delay for fully late jobs. The paper provides a formal definition of the late work parameter and compares the criteria based on it with other classical performance measures. It shows the relationship between the late work model and the imprecise computation model known from the hard real-time literature. Moreover, the paper presents a few real world applications of the late work objective function. The paper lists results obtained for nearly forty problems of scheduling jobs on a single machine, parallel (identical and uniform) machines and dedicated machines, investigated in the literature since 1984.     

Single machine batch scheduling with release times

Motivated by a high-throughput logging system, we investigate the single machine scheduling problem with batching, where jobs have release times and processing times, and batches require a setup time. Our objective is to minimize the total flow time, in the online setting. For the online problem where all jobs have identical processing times, we propose a 2-competitive algorithm and we prove a corresponding lower bound. Moreover, we show that if jobs with arbitrary processing times can be processed in any order, any online algorithm has a linear competitive ratio in the worst case. A preliminary version of a part of this paper was presented at the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006). We gratefully acknowledge reviewers’ comments that helped to improve the presentation of this work. Supported by the Swiss SBF under contract no. C05.0047 within COST-295 (DYNAMO) of the European Union. Research carried out while B. Weber was affiliated with the Institute of Theoretical Computer Science, ETH Zurich.     

A note on the complexity of the problem of two-agent scheduling on a single machine

We consider a two-agent scheduling problem on a single machine, where the objective is to minimize the total completion time of the first agent with the restriction that the number of tardy jobs of the second agent cannot exceed a given number. It is reported in the literature that the complexity of this problem is still open. We show in this paper that this problem is NP-hard under high multiplicity encoding and can be solved in pseudo-polynomial time under binary encoding. When the first agent's objective is to minimize the total weighted completion time, we show that the problem is strongly NP-hard even when the number of tardy jobs of the second agent is restricted to be zero.     

The price of fairness for a two-agent scheduling game minimizing total completion time

Journal of Combinatorial Optimization - This paper studies the price of fairness in a two-agent single machine scheduling game. In this game, two agents compete to perform their jobs on a common...     

On single machine scheduling with resource constraint

The single machine scheduling with resource constraint is a nonlinear combinatorial optimization problem in cloud computing applications. Given a set of jobs and certain resource, the problem is to find a permutation of jobs and a distribution of resource to optimize certain objective function. The processing time of each job is a nonlinear function with respect to the resource assigned to it. In this paper, we propose a naive algorithm and study a subproblem in the algorithm that suppose the permutation of jobs is also given, how to find a resource distribution to minimize the total weighted flow time. We found a polynomial-time optimal solution for a special case and an approximation solution in general case.     

MINIMIZING ABSOLUTE AND SQUARED DEVIATION OF COMPLETION TIMES FROM DUE DATES

This is a study of a single-machine scheduling problem with the objective of minimizing the sum of a function of earliness and tardiness called the earliness and tardiness (ET) problem. I will show that if priority weights of jobs are proportional to their processing times, and if earliness and tardiness cost functions are linear, the problem will be equivalent to the total weighted tardiness problem. This proves that the et problem is np -hard. In addition, I present a heuristic algorithm with worst case bound for the et problem based on the equivalence relation between the two. When earliness and tardiness cost functions are quadratic, I consider the problem for a common due date for all jobs and for different job due dates. In general, the et problem with quadratic earliness and tardiness cost functions and all job weights equal to one is np -hard. I show that in many cases, when weights of jobs are proportional to their processing times, the problem can be solved efficiently. In the published results on the et problem with quadratic earliness and tardiness cost functions other researchers have assumed a zero starting time for the schedule. I discuss the advantages of a nonzero starting time for the schedule.     

An Experimental Comparison of Time-Based and Economic-Based Scheduling Methods to Maximize Net Present Value*

In the past, performance in dynamic-scheduling environments was primarily measured in terms of time or physical shop characteristics. Objectives such as mean tardiness, flow time, and work-in-process inventory were commonly used. Today, there is increasing interest in the use of more advanced economic performance measures. These measures have the more comprehensive objective of maximizing ownership wealth by economically scheduling jobs and tasks. This study presents a large-scale experiment testing time-based and economic-based scheduling methods in a dynamic job shop. These methods are evaluated on their ability to maximize net present value (NPV). The study considers the just-in-time (JIT) delivery environment. The job shop is hypothetical, but is based on models of real production situations. Results show that the use of very detailed economic information in a sophisticated manner generally improves economic performance. Where due dates are easy to achieve, however, time-based scheduling methods are at least as good as those based on economics. Also, where utilization is high and due dates tight, early cost information in release and dispatch is detrimental to schedule value.     

A FRAMEWORK FOR MACHINE SCHEDULING PROBLEMS WITH CONTROLLABLE PROCESSING TIMES

This is a study of single and parallel machine scheduling problems with controllable processing time for each job. The processing time for job j depends on the position of the job in the schedule and is a function of the number of resource units allocated to its processing. Processing time functions and processing cost functions are allowed to be nonlinear. The scheduling problems considered here have important applications in industry and include many of the existing scheduling models as special cases. For the single machine problem, the objective is minimization of total compression costs plus a scheduling measure. The scheduling measures include makespan, total flow time, total differences in completion times, total differences in waiting times, and total earliness and tardiness with a common due date for all jobs. Except when the total earliness and tardiness measure is involved, each case the problem is solved efficiently. Under an assumption typically satisfied in just-in-time systems, the problem with total earliness and tardiness measure is also solved efficiently. Finally, for a large class of processing time functions; parallel machine problems with total flow time and total earliness and tardiness measures are solved efficiently. In each case we reduce the problem to a transportation problem.     

Multi-objective permutation flow shop scheduling problem: Literature review,classification and current trends

The flow shop scheduling problem is finding a sequence given n jobs with same order at m machines according to certain performance measure(s). The job can be processed on at most one machine; meanwhile one machine can process at most one job. The most common objective for this problem is makespan. However, many real-world scheduling problems are multi-objective by nature. Over the years there have been several approaches used to deal with the multi-objective flow shop scheduling problems (MOFSP). Hence, in this study, we provide a brief literature review of the contributions to MOFSP and identify areas of opportunity for future research.     

面向第4方物流的多代理人作业整合优化算法

物流作业整合是现代物流方法中减少物流成本的主要手段.在综合考虑代理商选择和线路优化两问题的基础上,建立了基于图状结构的面向第4方物流的多代理人作业整合优化模型.为了避免将代理商选择和线路优化作为两个互相分离的子问题来处理,提出了求解它的两层邻域搜索算法.第1层采用了转移、交换和环形移动3种移动策略求解作业在代理商之间的分配,而在第2层提出了路合并、路生成替换策略,形成了适于该问题的优化算法.随机产生20例算例,将两层邻域搜索算法的计算结果与基于k-最短路的枚举算法的计算结果进行比较,说明了该算法的可行性和有效性.     

Preemptive scheduling on two identical parallel machines with a single transporter

We consider a scheduling problem on two identical parallel machines, in which the jobs are moved between the machines by an uncapacitated transporter. In the processing preemption is allowed. The objective is to minimize the time by which all completed jobs are collected together on board the transporter. We identify the structural patterns of an optimal schedule and design an algorithm that either solves the problem to optimality or in the worst case behaves as a fully polynomial-time approximation scheme.     

A memetic differential evolution algorithm for energy-efficient parallel machine scheduling

This paper considers an energy-efficient bi-objective unrelated parallel machine scheduling problem to minimize both makespan and total energy consumption. The parallel machines are speed-scaling. To solve the problem, we propose a memetic differential evolution (MDE) algorithm. Since the problem involves assigning jobs to machines and selecting an appropriate processing speed level for each job, we characterize each individual by two vectors: a job-machine assignment vector and a speed vector. To accelerate the convergence of the algorithm, only the speed vector of each individual evolves and a list scheduling heuristic is applied to derive its job-machine assignment vector based on its speed vector. To further enhance the algorithm, we propose efficient speed adjusting and job-machine swap heuristics and integrate them into the algorithm as a local search approach by an adaptive meta-Lamarckian learning strategy. Computational results reveal that the incorporation of list scheduling heuristic and local search greatly strengthens the algorithm. Computational experiments also show that the proposed MDE algorithm outperforms SPEA-II and NSGA-II significantly.     

The Flow Shop Scheduling Polyhedron with Setup Times

This paper addresses the problem of improving the polyhedral representation of a certain class of machine scheduling problems. Despite the poor polyhedral representation of many such problems in general, it is shown that notably tighter linear programming representations can be obtained for many important models. In particular, we study the polyhedral structure of two different mixed-integer programming formulations of the flow shop scheduling problem with sequence-dependent setup times, denoted by SDST flow shop. The first is related to the asymmetric traveling salesman problem (ATSP) polytope. The second is less common and is derived from a model proposed by Srikar and Ghosh based on the linear ordering problem (LOP) polytope. The main contribution of this work is the proof that any facet-defining inequality (facet) of either of these polytopes (ATSP and LOP) induces a facet for the corresponding SDST flow shop polyhedron. The immediate benefit of this result is that all developments to date on facets and valid inequalities for both the ATSP and the LOP can be applied directly to the machine scheduling polytope. In addition, valid mixed-integer inequalities based on variable upper-bound flow inequalities for either model are developed as well. The derived cuts are evaluated within a branch-and-cut framework.