Ordinal On-Line Scheduling for Maximizing the Minimum Machine Completion Time

This paper considers the on-line problem of scheduling nonpreemptively n independent jobs on m > 1 identical and parallel machines with the objective to maximize the minimum machine completion time. It is assumed that the values of the processing times are unknown but the order of the jobs by their processing times is known in advance. We are asked to decide the assignment of all the jobs to some machines at time zero by utilizing only ordinal data rather than the actual magnitudes of jobs. Algorithms to slove the problem are called ordinal algorithms. In this paper, we give lower bounds and ordinal algorithms. We first propose an algorithm MIN which is at most -competitive for any m machine case, while the lower bound is _i=1 ^m 1/i. Both are on the order of (ln m). Furthermore, for m = 3, we present an optimal algorithm.     

基于峰值负荷的签派员席位任务分配问题

本文研究的问题来源于航空公司运行控制中心的签派部门,签派员在放行航班时,既要保证航班的正点起飞,又要调节放行航班的工作劳动强度保证放行的质量,使航班在安全状态下运行。这里放行航班的工作劳动强度为单位时间内的工作时间,峰值负荷即劳动强度最大值。峰值负荷过高则工作紧张,进而推断该放行席位的任务分配不合理。文中将问题描述为任务有优先序的单机排序问题,每个任务都有一个到达时间（release time）、截止期限（deadline）和处理时间（procession time）,处理时间因任务的不同而不同,目标是在绝对不准延误完成任务前提下,使单位时间的峰值负荷最小。在使单位时间峰值负荷最小的目标下,本文提出了一个有效算法,并证明该算法下的任务安排是最优安排。     

An online algorithm for continuous slab caster scheduling

Lee et al. (Lee, K., Chang, S.Y., and Hong, Y., 2004. Continuous slab caster scheduling and interval graphs. Production Planning & Control, 13 (5), 495–501) have introduced a slab caster scheduling problem and developed an optimal algorithm. Their algorithm is efficient but an offline algorithm that we need the information on all the customer orders a priori to implement. In this article, we propose an online algorithm that we can implement without knowledge of the orders yet to arrive. We show that the offline version of our new algorithm also provides an optimal solution and the online version has the worst case performance ratio of 3. We also give a short proof on the correctness of Lee et al.'s algorithm.     

A Multi-Exchange Neighborhood for Minimum Makespan Parallel Machine Scheduling Problems

We propose new local search algorithms for minimum makespan parallel machine scheduling problems, which perform multiple exchanges of jobs among machines. Inspired by the work of Thompson and Orlin (1989) on cyclic transfer neighborhood structures, we model multiple exchanges of jobs as special disjoint cycles and paths in a suitably defined improvement graph, by extending definitions and properties introduced in the context of vehicle routing problems (Thompson and Psaraftis, 1993) and of the capacitated minimum spanning tree problem (Ahuja et al., 2001). Several algorithms for searching the neighborhood are suggested.We report the results of a wide computational experimentation, on different families of benchmark instances, performed for the case of identical machines. This problem has been selected as a case study to perform a comparison among the alternative algorithms, and to discover families of instances for which the proposed neighborhood may be promising in practice. Based on the results of the experiments, we can suggest which among the many possible variants of the proposed approaches may be more promising for developing local search algorithms based on multi-exchange moves for related problems. Also, on some families of instances, which are very hard to solve exactly, the most promising multi-exchange algorithms were observed to dominate, in solution quality and in computational time, competitive benchmark heuristics.     

Analysis of the List Scheduling Algorithm for Precedence Constrained Parallel Tasks

Given P processors, and a set of precedence constrained parallel tasks with their processor requirements and execution times, the problem of scheduling precedence constrained parallel tasks on multiprocessors is to find a nonpreemptive schedule of the tasks on a multiprocessor with P processors, such that the schedule length is minimized. We show that for many heuristic choices of the initial priority list, the list scheduling algorithm has worst-case performance ratio P, which is unbounded as P gets large. However, it is also shown that when task sizes are bounded from above by a fraction of P, the list scheduling algorithm has finite worst-case performance ratio. In particular, we prove that if all tasks request for no more than qP processors, where 0 < q < 1, then the worst-case performance ratio of the list scheduling algorithm is no larger than

面向成套订单问题的工艺规划与排序的集成研究

本文从工艺规划与排序的集成优化角度研究了成套订单问题^[1],克服了单独研究工艺规划和排序局部优化的局限性.文章中考虑了同一工件内部各道工序之间存在的优先加工限制,以及工件在不同机器上加工需要转移时间和工序间接连加工需要机器调整时间的情况,建立了成套订单问题的集成排序模型,并提出了针对求解大规模问题的基于遗传算法的启发式算法,最后通过一个算例对所研究的集成排序问题和所提出的算法进行了说明,计算结果表明了算法的有效性.     

Performance ratios of the Karmarkar-Karp differencing method

We consider the multiprocessor scheduling problem in which one must schedule n independent tasks nonpreemptively on m identical, parallel machines, such that the completion time of the last task is minimal. For this well-studied problem the Largest Differencing Method of Karmarkar and Karp outperforms other existing polynomial-time approximation algorithms from an average-case perspective. For m ≥ 3 the worst-case performance of the Largest Differencing Method has remained a challenging open problem. In this paper we show that the worst-case performance ratio is bounded between . For fixed m we establish further refined bounds in terms of n.     

Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts

For an edge weighted undirected graph G and an integer k > 2, a k-way cut is a set of edges whose removal leaves G with at least k components. We propose a simple approximation algorithm to the minimum k-way cut problem. It computes a nearly optimal k-way cut by using a set of minimum 3-way cuts. We show that the performance ratio of our algorithm is 2 – 3/k for an odd k and 2 – (3k – 4)/(k ² – k) for an even k. The running time is O(kmn ³ log(n ²/m)) where n and m are the numbers of vertices and edges respectively.     

On-Line Scheduling of Two-Machine Open Shops Where Jobs Arrive Over Time

We investigate the problem of on-line scheduling two-machine open shops with the objective of minimizing the makespan.Jobs arrive independently over time, and the existence of a job is not known until its arrival. In the clairvoyant on-line model, the processing requirement of every job becomes fully known at the arrival of the job, while inthe non-clairvoyant on-line model, this processing requirement is notknown until the job is processed and completed.In both models, scheduling of a job is irrevocable.We study the two-machine open shop problem for both models in the preemptive and in the non-preemptive version. For each of the four variants, we provide an algorithm that is best possible with respect to the worst-case performance. In the clairvoyant on-line model, the best worst-case performance ratios are 5/4 (preemptive) and 3/2 (non-preemptive), and in the non-clairvoyant on-line model, they are 3/2 (preemptive and non-preemptive).     

A Framework for the Complexity of High-Multiplicity Scheduling Problems

The purpose of this note is to propose a complexity framework for the analysis of high multiplicity scheduling problems. Part of this framework relies on earlier work aiming at the definition of output-sensitive complexity measures for the analysis of algorithms which produce “large” outputs. However, different classes emerge according as we look at schedules as sets of starting times, or as related single-valued mappings.     

Integrated Order Scheduling and Packing

We consider an integrated production–distribution scheduling model in a make‐to‐order supply chain consisting of one supplier and one customer. The supplier receives a set of orders from the customer at the beginning of a planning horizon. The supplier needs to process all the orders at a single production line, pack the completed orders to form delivery batches, and deliver the batches to the customer. Each order has a weight, and the total weight of the orders packed in a batch must not exceed the capacity of the delivery batch. Each delivery batch incurs a fixed distribution cost. The problem is to find jointly a schedule for order processing and a way of packing completed orders to form delivery batches such that the total distribution cost (or equivalently, the number of delivery batches) is minimized subject to the constraint that a given customer service level is guaranteed. We consider two customer service constraints—meeting the given deadlines of the orders; or requiring the average delivery lead time of the orders to be within a given threshold. Several problems of the model with each of those constraints are considered. We clarify the complexity of each problem and develop fast heuristics for the NP‐hard problems and analyze their worst‐case performance bounds. Our computational results indicate that all the heuristics are capable of generating near optimal solutions quickly for the respective problems.     

Online scheduling on parallel machines with two GoS levels

This paper investigates the online scheduling problem on parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. Hence each job and machine are labeled with the GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine. The goal is to minimize the makespan. In this paper, we consider the problem with two GoS levels. It assumes that the GoS levels of the first k machines and the last m−k machines are 1 and 2, respectively. And every job has a GoS level of 1 alternatively or 2. We first prove the lower bound of the problem under consideration is at least 2. Then we discuss the performance of algorithm AW presented in Azar et al. (J. Algorithms 18:221–237, 1995) for the problem and show it has a tight bound of 4−1/m. Finally, we present an approximation algorithm with competitive ratio . Research supported by Natural Science Foundation of Zhejiang Province (Y605316) and its preliminary version appeared in Proceedings of AAIM2006, LNCS, 4041, 11-21.     

具有概率分布在线租赁问题策略研究

在经济系统中,决策越来越呈现出在线性特征,传统优化方法在解决这类在线问题时,通常假设未来输入是一随机变量从而寻求概率意义上的最优决策。近年来,在优化领域兴起了一种新的研究方法——在线算法与竞争分析,为解决这类在线问题提供了新的视角,但传统的竞争分析方法有意规避概率分布假设。对于在线租赁决策问题,由于其输入结构简单且具有良好的统计性质,似乎忽略这些有用的信息而只运用标准的竞争比方法分析显然具有不足之处。在本文中,我们将其输入结构的概率分布引入纯竞争分析方法中,从而建立了具有概率情形的最优在线租赁模型,并得到了最优竞争策略及其竞争比。     

A memetic algorithm for the patient transportation problem

This paper addresses a real-life public patient transportation problem derived from the Hong Kong Hospital Authority (HKHA), which provides ambulance transportation services for disabled and elderly patients from one location to another. We model the problem as a multi-trip dial-a-ride problem (MTDARP), which requires designing several routes for each ambulance. A route is a sequence of locations, starting and terminating at the depot (hospital), according to which the ambulance picks up clients at the origins and delivers them to the destinations. A route is feasible only if it satisfies a series of side constraints, such as the pair and precedence constraints, capacity limit, ride time, route duration limit and time windows. Owing to the route duration limit, in particular, every ambulance is scheduled to operate several routes during the working period. To prevent the spread of disease, the interior of the ambulances needs to be disinfected at the depot between two consecutive trips. The primary aim of the problem investigated herein is to service more requests with the given resources, and to minimize the total travel cost for the same number of requests. In this paper, we provide a mathematical formulation for the problem and develop a memetic algorithm with a customized recombination operator. Moreover, the segment-based evaluation method is adapted to examine the moves quickly. The performance of the proposed algorithm is assessed using the real-world data from 2009 and compared with results obtained by solving the mathematical model. In addition, the proposed algorithm is adapted to solve the classic DARP instances, and found to perform well on medium-scale instances.     

基于风险的考虑成本和允许等待的车辆运输调度问题研究

本文同时考虑了成本约束和允许等待情形,研究了最小化风险的车辆运输调度问题,其中运输风险是随时间不同而变化的,即研究在时间依赖网络中基于风险的有约束的运输路径选择问题,以及在选定路径的顶点上决定的出发和等待时间的综合问题。建立了相应的混合整数规划模型,设计了相应的算法,并分析了算法复杂性,最后通过算例验证了该算法的有效性和可行性。     

Analytic evaluation of the expectation and variance of different performance measures of a schedule on a single machine under processing time variability

In this paper, we present closed-form expressions, wherever possible, or devise algorithms otherwise, to determine the expectation and variance of a given schedule on a single machine. We consider a variety of completion time and due date-based objectives. The randomness in the scheduling process is due to variable processing times with known means and variances of jobs and, in some cases, a known underlying processing time distribution. The results that we present in this paper can enable evaluation of a schedule in terms of both the expectation and variance of a performance measure considered, and thereby, aid in obtaining a stable schedule. Additionally, the expressions and algorithms that are presented, can be incorporated in existing scheduling algorithms in order to determine expectation-variance efficient schedules.     

基于任务跟踪的在线租赁问题与竞争策略研究

现实经济活动中,有许多租赁融资决策既非纯在线租赁问题也非纯离线租赁问题,而是介于二者之间的具有部分已知信息的在线租赁问题.基于此研究了工作任务总量已知而工作任务进展序列未知的在线设备租赁问题,以租赁工作所需设备的费用最小为优化目标,建立了该问题的基本数学模型,提出了任务跟踪策略,给出并证明了基于这一策略的算法的竞争比.最后,把该在线租赁问题的竞争比与经典的在线租赁问题的竞争比做了比较分析,结果表明在线租赁问题的算法优于经典的在线算法,竞争性能得到了较大的提高.     

Minimizing the Number of Late Jobs under the Group Technology Assumption

We consider the one-machine scheduling problem to minimize the number of late jobs under the group technology assumption, where jobs are classified into groups and all jobs from the same group must be processed contiguously. This problem is shown to be strongly NP-hard, even for the case of unit processing time and zero set-up time. A polynomial time algorithm is developed for the restricted version in which the jobs in each group have the same due date. However, the problem is proved to be ordinarily NP-hard if the jobs in a group have the same processing time as well as the same due date.     

An estimation of distribution algorithm for lot-streaming flow shop problems with setup times

Lot-streaming flow shops have important applications in different industries including textile, plastic, chemical, semiconductor and many others. This paper considers an n-job m-machine lot-streaming flow shop scheduling problem with sequence-dependent setup times under both the idling and no-idling production cases. The objective is to minimize the maximum completion time or makespan. To solve this important practical problem, a novel estimation of distribution algorithm (EDA) is proposed with a job permutation based representation. In the proposed EDA, an efficient initialization scheme based on the NEH heuristic is presented to construct an initial population with a certain level of quality and diversity. An estimation of a probabilistic model is constructed to direct the algorithm search towards good solutions by taking into account both job permutation and similar blocks of jobs. A simple but effective local search is added to enhance the intensification capability. A diversity controlling mechanism is applied to maintain the diversity of the population. In addition, a speed-up method is presented to reduce the computational effort needed for the local search technique and the NEH-based heuristics. A comparative evaluation is carried out with the best performing algorithms from the literature. The results show that the proposed EDA is very effective in comparison after comprehensive computational and statistical analyses.     

Closed-Form Deterministic End-to-End Performance Bounds for the Generalized Processor Sharing Scheduling Discipline

The Generalized Processor Sharing (GPS) schedulingdiscipline is an important scheduling mechanism that can support both class isolation and bandwidth sharing among different service classes, thus making itan appealing choice for networks providing multiple services with Quality-of-Service guarantees. In this paper, we study a broad classof GPS networks known as Consistent Relative Session Treatment}(CRST) GPS networks and establish closed-form end-to-end performance boundsfor CRST GPS networks. This result generalizes the results of Parekhand Gallager (1994) where simple, closed-form end-to-end performancebounds are derived for a special sub-class of CRST GPS networks, theso-called Rate Proportional Processor Sharing (RPPS) GPS networks, but performance bounds for the general CRST GPS networks do not haveclosed-form. Our result is obtained through the notion of CRSTpartition, which in fact yields a broader class of CRST GPS networksthan the one originally defined in (Parekh and Gallager, 1993). Moreover,our approach is quite general. It not only applies to the deterministicanalysis of GPS networks, but can also be employed in the study of GPSnetworks in a stochastic setting.