Preemptive and Non-preemptive On-line Algorithms for Scheduling with Rejection on Two Uniform Machines

In this paper, we consider the problem of on-line scheduling a job sequence on two uniform machines. A job can be either rejected, in which case we pay its penalty, or scheduled on machines, in which case it contributes its processing time to the makspan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule for all accepted jobs and the penalties of all rejected jobs. Both preemptive and non-preemptive versions are considered. For the preemptive version, we present an optimal on-line algorithm with a competitive ratio for any s≥1, where s is the machine speed ratio. For the non-preemptive version, we present an improved lower bound. Moreover, as an optimal algorithm for s≥1.6180 is known, we present a modified version of the known algorithm, and show that it becomes optimal for any 1.3852≤s<1.6180 and has a smaller competitive ratio than that of original version for any 1≤s<1.3852. The maximum gap between its competitive ratio and the lower bound is 0.0534.     

Semi On-Line Scheduling on Two Identical Machines

This paper investigates two different semi on-line scheduling problems on a two-machine system. In the first case, we assume that all jobs have their processing times in between p and rp . In the second case, we assume that the largest processing time is known in advance. We show that one has a best possible algorithm with worst case ratio 4/3 while LS is still the best possible for the other problem with ratio which is still in the worst case . Received: February 23, 1998; revised August 5, 1998     

A note on MULTIFIT scheduling for uniform machines

In this note, we derive the tight worst case bound √6/2+(1/2) ^k for scheduling with the MULTIFIT heuristic on two parallel uniform machines withk calls of FFD within MULTIFIT. When MULTIFIT is combined with LPT as an incumbent algorithm the worst case bound decreases to √2+1/2+(1/2) ^k . Partially supported by SFB F003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung and by the National Natural Science Foundation of China, Grant 19701028.     

Scheduling Problems on Two Sets of Identical Machines

In this paper we investigate the following scheduling problem: We have two sets of identical machines, the jobs have two processing times one for each set of machines. We consider two different objective functions, in the first model the goal is to minimize the maximum of the makespans on the sets, in the second model we minimize the sum of the makespans. We consider the online, semi online and offline versions of these problems. This research has been partially supported by the Future and Emerging Technologies programme of the EU under contract number IST-1999-14186 (ALCOM-FT) and by the Hungarian National Foundation for Scientific Research, Grant TO30074. During some part of this work the author had a postdoctoral scholarship at MPI Informatics in Saarbrücken.     

Parameterized on-line open-end bin packing

This note deals with a new variant of bin packing, the so-called open-end bin packing problem in which a bin can be filled to a level exceeding its capacity by its last item if it is not full immediately before the last is packed. We investigate the on-line version of this problem and give best possible algorithms for parametric cases. This work is supported by the Foundation under State Education Committee of China.     

A linear algorithm for the pos/neg-weighted 1-median problem on a cactus

The 1-median problem on a network asks for a vertex minimizing the sum of the weighted shortest path distances from itself to all other vertices, each associated with a certain positive weight. We allow fornegative weights as well and devise an exact algorithm for the resulting ‘pos/neg-weighted’ problem defined on a cactus. The algorithm visits every vertex just once and runs thus in linear time. This research has been supported by the Spezialforschungsbereich F 003 ‘Optimierung und Kontrolle’, Projektbereich Diskrete Optimierung.     

Tighter Bounds on Preemptive Job Shop Scheduling with Two Machines

We consider the preemptive job shop scheduling problem with two machines, with the objective to minimize the makespan. We present an algorithm that finds a schedule of length at most P _max/2 greater than the optimal schedule length, where P _max is the length of the longest job. Received June 13, 2000     

Solution methods and computational investigations for the Linear Bottleneck Assignment Problem

The Linear Bottleneck Assignment ProblemLBAP is analyzed from a computational point of view. Beside a brief review of known algorithms new methods are developed using only sparse subgraphs for their computation. The practical behaviour of both types of algorithms is investigated. The most promising algorithm consists of computing a maximum cardinality matching with all edge costs smaller than a previously determined bound and augmenting this matching to an assignment. The methods on sparse subgraphs are useful in the case of memory restrictions and are superior if the subgraph selection can be improved by some previously generated structure. Other treated questions are how to select a suitable subgraph for the new methods, how to deal with non regular data and what connections to asymptotic results for theLBAP can be detected. Supported by the SFB F003 ‘Optimierung und Kontrolle’, Bereich Diskrete Optimierung.     

Maintenance routing for train units: The interchange model

Train units need regular preventive maintenance. Given the train units that require maintenance in the forthcoming 1–3 days, the rolling stock schedule must be adjusted so that these urgent units reach the maintenance facility in time. In this paper, we present an integer programming model for solving this problem, give complexity results, suggest solution methods, and report our computational results based on practical instances of NS Reizigers, the main Dutch operator of passenger trains.     

On the Complexity of Non-preemptive Shop Scheduling with Two Jobs

In this note, we investigate the time complexity of non-preemptive shop scheduling problems with two jobs. First we study mixed shop scheduling where one job has a fixed order of operations and the operations of the other job may be executed in arbitrary order. This problem is shown to be binary NP-complete with respect to all traditional optimality criteria even if distinct operations of the same job require different machines. Moreover, we devise a pseudo-polynomial time algorithm which solves the problem with respect to all non-decreasing objective functions. Finally, when the job with fixed order of operations may visit a machine more than once, the problem becomes unary NP-complete. Then we discuss shop scheduling with two jobs having chain-like routings. It is shown that the problem is unary NP-complete with respect to all traditional optimality criteria even if one of the jobs has fixed order of operations and the jobs cannot visit a machine twice. Received July 28, 2001; revised May 15, 2002 Published online: July 26, 2002     

An exterior simplex type algorithm for the Minimum Cost Network Flow Problem

In this paper a new Network Exterior Point Simplex Algorithm (NEPSA) for the Minimum Cost Network Flow Problem (MCNFP) is analytically presented. NEPSA belongs to a special simplex type category and is a modification of the classical network simplex algorithm. The main idea of the algorithm is to compute two flows. One flow is basic but not always feasible and the other is feasible but not always basic. A complete proof of correctness for the proposed algorithm is also presented. Moreover, the computational behavior of NEPSA is shown by an empirical study carried out for randomly generated sparse instances created by the well-known GRIDGEN network problem generator.     

A Dual Framework for Lower Bounds of the Quadratic Assignment Problem Based on Linearization

A dual framework allowing the comparison of various bounds for the quadratic assignment problem (QAP) based on linearization, e.g. the bounds of Adams and Johnson, Carraresi and Malucelli, and Hahn and Grant, is presented. We discuss the differences of these bounds and propose a new and more general bounding procedure based on the dual of the linearization of Adams and Johnson. The new procedure has been applied to problems of dimension up to , and the computational results indicate that the new bound competes well with existing linearization bounds and yields a good trade off between computation time and bound quality. Received: February 5, 1999; revised August 24, 1999     

An improved algorithm for the p-center problem on interval graphs with unit lengths

The p-center problem is to locate p facilities in a network of n   demand points so as to minimize the longest distance between a demand point and its nearest facility. We consider this problem by modelling the network as an interval graph whose edges all have unit lengths. We present an O(n)$O(n)$ time algorithm for the problem under the assumption that the endpoints of the intervals are sorted, which improves on the existing best algorithm for the problem that has a run time of O(pn)$O(\mathit{pn})$.     

A linear compound algorithm for uniform machine scheduling

In this paper, we consider the classical two uniform machine scheduling problem. We present a compound algorithm which consists of three Greedy-like subprocedures running independently. We prove that the algorithm has a worst-case bound of 7/6 and runs in linear time. Partially supported by SFB F003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung and by the National Natural Science Foundation of China.     

Volume Maximization and Orthoconvex Approximation of Orthogons

Let n axes-parallel hyperparallelepipeds (also called blocks) of the d-dimensional Euclidean space and a positive integer r be given. The volume maximization problem (VMP) selects at most r blocks such that the volume of their union becomes maximum. VMP is shown to be -hard in the 2-dimensional case and polynomially solvable for the line via a constrained critical path problem (CCPP) in an acyclic digraph. This CCPP leads to further well solvable special cases of the maximization problem. In particular, the following approximation problem (OAP) becomes polynomially solvable: given an orthogon P (i.e., a simple polygon in the plane which is a union of blocks) and a positive integer q, find an orthoconvex orthogon with at most q vertices and minimum area, which contains P. Received: September 7, 1998     

Makespan minimization in preemptive two machine job shops

In this note we investigate the NP-complete problem of minimizing the makespan in a preemptive two machine job shop. We present a polynomial time approximation algorithm with worst case ratio 3/2 for this problem, and we also argue that this is the best possible result that can be derived via our line of approach.     

Preemptive Scheduling on Uniform Parallel Machines with Controllable Job Processing Times

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.     

Constructing finite algebras with FALCON

The generation of models and counterexamples is an important form of reasoning. In this paper, we give a formal account of a system, called FALCON, for constructing finite algebras from given equational axioms. The abstract algorithms, as well as some implementation details and sample applications, are presented. The generation of finite models is viewed as a constraint satisfaction problem, with ground instances of the axioms as constraints. One feature of the system is that it employs a very simple technique, called the least number heuristic, to eliminate isomorphic (partial) models, thus reducing the size of the search space. The correctness of the heuristic is proved. Some experimental data are given to show the performance and applications of the system.     

基于S3C4510B芯片KVM虚拟机的移植和测试

本文简单介绍S3C4510B芯片、uClinux操作系统、适合于平台各异，网络条件相对较差的嵌入式Java虚拟机-KVM。给出了KVM移植到S3C4510B芯片上的uClinux操作系统的方案、具体实现过程、功能测试和性能测试。     

Optimal On-Line Algorithms to Minimize Makespan on Two Machines with Resource Augmentation

We study the problem of on-line scheduling on two uniformly related machines where the on-line algorithm has resources different from those of the off-line algorithm. We consider three versions of this problem, preemptive semi-online, non-preemptive on-line and preemptive on-line scheduling. For all these cases we design algorithms with best possible competitive ratios as functions of the machine speeds. This work was submitted as a part of the M.Sc. thesis of the second author. A preliminary version of this paper appeared in the proceedings of The First Workshop on Approximation and Online Algorithms (WAOA’03), pages 109–122.