一个不同时刻加工成本有差异的单机排序问题

考虑一个单机排序问题:一批工件在零时刻到达可加工,加工时不可中断,在某个给定时间区间外的加工工时将招致额外的加工成本;当时间区间为给定参数时,要求确定一个最优加工序,当时间区间为决策变量时,要求找到一个最优序及最优区间位置, 由此来最小化总额外加工成本．文中对各种区间外单位加工工时之额外成本的情况给出了多项式算法, NP-hardness的证明及伪多项式时间算法．     

Improved algorithm for a generalized on-line scheduling problem on identical machines

This paper considers the problem of on-line scheduling a list of independent jobs in which each job has an arbitrary release time on m parallel identical machines. In this problem, jobs arrive in form of order before its release time and decisions have to be made whenever an order is placed and the orders arrive according to any sequence. A heuristic algorithm, NMLS, better than MLS is given for any m ? 2. The competitive ratio is improved from 2.93920 to 2.78436.     

关于排序模型1|·|r_i≥0| sum from i=1 to n v_i的注记(英文)

设J={J1,…,Jn}是n个工件的集合,M是一台机器.每个工件Ji要在机器M上加工一次,而且是相继只加工一次,即加工不能够中断.Ji的加工时间是pi,准备时间是ri,即Ji不能在ri之前加工,要求完工的期限是di,即工件Ji的加工应该在di之前完成.否则,这个工件将被拒绝放在一旁.我们的目的是寻找排序算法A,当使用到给定的J上时,使被拒绝的工件个数为最少.1978年Kise,Ibaraki,Mine等在条件ri相似文献   

Mutual exclusion scheduling with interval graphs or related classes: Complexity and algorithms

This note summarizes the main results presented in the author's Ph.D. thesis, supervised by Professor Michel Van Caneghem and defended on 14th June 2005 at University of Aix-Marseille II, France. The thesis, written in French, is available at http: //www.lif-sud.univ-mrs.fr/Rapports/25-2005.html. The mutual exclusion scheduling problem has an elegant graph-theoretic formulation: given an undirected graph G and an integer k, find a minimum coloring of G such that each color appears at most k times. When G is an interval graph, this problem has some applications in workforce planning. Then, the object of the thesis is to study the complexity of mutual exclusion scheduling problem for interval graphs and related classes. Received: August 2005 / Revised version: September 2005 Frédéric Gardi: On leave from Laboratoire d'Informatique Fondamentale - CNRS UMR 6166, Parc Scientifique et Technologique de Luminy, Marseille, France.     

Preemptive scheduling and antichain polyhedra

We present a theoretical framework, which is based upon notions of ordered hypergraphs and antichain polyhedra, and which is dedicated to the combinatorial analysis of preemptive scheduling problems submitted to parallelization constraints.This framework allows us to characterize specific partially ordered structures which are such that induced preemptive scheduling problems may be solved through linear programming. To prove that, in the general case, optimal preemptive schedules may be searched inside some connected subset of the vertex set of an Antichain Polyhedron.     

Balanced home–away assignments

In recent years several approaches for generating sports league schedules have been proposed. In this paper we consider foundations for a two-stage approach to construct schedules for a single round robin tournament (or the first half series of a double round robin tournament). In the first stage for each game a mode (home or away) has to be determined and in the second stage the games have to be scheduled in their assigned modes. We study a problem of the first stage where balanced home–away assignments have to be constructed such that for each team the numbers of home and away games differ by at most one. After showing that it is easy to construct balanced home–away assignments we propose repairing mechanisms for unbalanced home–away assignments. Then, neighborhoods on the set of balanced home–away assignments are defined which are shown to be connected. Finally, situations with preassignments are studied.     

Airline crew scheduling from planning to operations

Crew scheduling problems at the planning level are typically solved in two steps: first, creating working patterns, and then assigning these to individual crew. The first step is solved with a set covering model, and the second with a set-partitioning model. At the operational level, the (re) planning period is considerably smaller than during the strategic planning phase. We integrate both models to solve time critical crew recovery problems arising on the day of operations. We describe how pairing construction and pairing assignment are done in a single step, and provide solution techniques based on simple tree search and more sophisticated column generation and shortest-path algorithms.     

Approximability of flow shop scheduling

Shop scheduling problems are notorious for their intractability, both in theory and practice. In this paper, we construct a polynomial approximation scheme for the flow shop scheduling problem with an arbitrary fixed number of machines. For the three common shop models (open, flow, and job), this result is the only known approximation scheme. Since none of the three models can be approximated arbitrarily closely in the general case (unless P = NP), the result demonstrates the approximability gap between the models in which the number of machines is fixed, and those in which it is part of the input of the instance. The result can be extended to flow shops with job release dates and delivery times and to flow shops with a fixed number of stages, where the number of machines at any stage is fixed. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper appeared in theProceedings of the 36th Annual IEEE Symposium on the Foundations of Computer Science, 1995.Research supported by NSF grant DMI-9496153.     

两种运输方式下的船只优化排序模型及算法

本文讨论的是在两种不同容量的船只和两条不同运输路线的情况下的库存与运输联合优化排序问题.传统的经济批量订货问题里每次定购成本固定不变,而我们的问题里面定购成本是阶跃式的,与使用的船数相关.以往运输网络优化的论文都只考虑一种容量的运输工具,没有考虑不同容量的运输工具.本文结合这两方面做了进一步的研究,并根据实际应用背景建立了数学模型,讨论最优解的性质,由最优解性质给出了复杂度为O(N4) 的多项式算法.     

Vehicle routing problems on a line-shaped network with release time constraints

This work considers the vehicle routing problem on a line with the constraint that each customer is visited after its release time. It is already known that the single-vehicle case is polynomially solvable. We present polynomial time algorithms for two variants of the multi-vehicle case.