4000197
Lot-sizing scheduling with batch setup times
This paper is concerned with scheduling independent jobs on m parallel machines in such a way that the makespan is minimized. Each job j is allowed to split arbitrarily into several parts, which can be individually processed on any machine at any time. However, a setup for uninterrupted sj time units is required before any split part of job j can be processed on any machine. The problem is strongly NP-hard if the number m of machines is variable and weakly NP-hard otherwise. We give a polynomial-time $$\frac{5}{3}$$-approximation algorithm for the former case and a fully polynomial-time approximation scheme for the latter.
4020261
On-Line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time
Scheduling a batch processing system has been extensively studied in the last decade. A batch processing system is modelled as a machine that can process up to b jobs simultaneously as a batch. The scheduling problem involves assigning all n jobs to batches and determining the batch sequence in such a way that certain objective function of job completion times Cj is minimized. In this paper, we address the scheduling problem under the on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job that may arrive later. Our objective is to minimize the total weighted completion time ∑wjCj. We provide a linear time on-line algorithm for the unrestrictive model (i.e., b ≥ n) and show that the algorithm is 10/3-competitive. For the restrictive model (i.e., b < n), we first consider the (off-line) problem of finding a maximum independent vertex set in an interval graph with cost constraint (MISCP), which is NP-hard. We give a dual fully polynomial time approximation scheme for MISCP, which leads us to a (4 + ∈)-competitive on-line algorithm for any ∈ > 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees.
4028543
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).
39846081
On-Line Algorithms for Cardinality Constrained Bin Packing Problems
The bin packing problem asks for a packing of a list of items from [0, 1] into the smallest possible number of bins having unit capacity. The k-item bin packing problem additionally imposes the constraint that at most k items are allowed in one bin. We present two efficient approximation algorithms for the on-line version of this problem. We show that, for increasing values of k, the asymptotic worst-case performance ratio of the first algorithm tends towards 2 and that the second algorithm has an asymptotic worst-case performance ratio of 2. Both heuristics considerably improve upon the best known result 2.7 of Krause, Shen and Schwetman. Moreover, we present algorithms for k = 2 and k = 3, where the result for k = 2 is best possible.
2045915
A Web-based Demonstrator of a Multi-lingual Phrase-based Translation System
This paper describes a multi-lingual phrase-based Statistical Machine Translation system accessible by means of a Web page. The user can issue translation requests from Arabic, Chinese or Spanish into English. The same phrase-based statistical technology is employed to realize the three supported language-pairs. New language-pairs can be easily added to the demonstrator. The Web-based interface allows the use of the translation system to any computer connected to the Internet.
6763688
Paint Inspired Color Mixing and Compositing for Visualization
Color is often used to convey information, and color compositing is often required while visualizing multiattribute information. This paper proposes an alternative method for color compositing. In order to present understandable color blending to the general public, several techniques are proposed. First, a paint-inspired RYB color space is used. In addition, noise patterns are employed to produce subregions of pure color within an overlapped region. We show examples to demonstrate the effectiveness of our technique for visualization
42441601
Hamiltonian uniform subset graphs
The uniform subset graph G(n, k, t) is defined to have all k-subsets of an n-set as vertices and edges joining k-subsets intersecting at t elements. We conjecture that G(n, k, t) is hamiltonian when it is different from the Petersen graph and does possess cycles. We verify this conjecture for k − t = 1, 2, 3 and for suitably large n when t = 0, 1.
16547141
Edge domination in complete partite graphs
Abstract An edge dominating set in a graph G is a set of edges D such that every edge not in D is adjacent to an edge of D . An edge domatic partition of a graph G =( V , E ) is a collection of pairwise-disjoint edge dominating sets of G whose union is E . The maximum size of an edge domatic partition of G is called the edge domatic number . In this paper, we study the edge domatic number of the complete partite graphs and give the answers for balanced complete partite graphs and complete split graphs .
11015337
Composite subset measures
Measures are numeric summaries of a collection of data records produced by applying aggregation functions. Summarizing a collection of subsets of a large dataset, by computing a measure for each subset in the (typically, user-specified) collection is a fundamental problem. The multidimensional data model, which treats records as points in a space defined by dimension attributes, offers a natural space of data subsets to be considered as summarization candidates, and traditional SQL and OLAP constructs, such as GROUP BY and CUBE, allow us to compute measures for subsets drawn from this space. However, GROUP BY only allows us to summarize a limited collection of subsets, and CUBE summarizes all subsets in this space. Further, they restrict the measure used to summarize a data subset to be a one-step aggregation, using functions such as SUM, of field-values in the data records.In this paper, we introduce composite subset measures, computed by aggregating not only data records but also the measures of other related subsets. We allow summarization of naturally related regions in the multidimensional space, offering more flexibility than either GROUP BY or CUBE in the choice of what data subsets to summarize. Thus, our framework allows more meaningful summaries to be computed for a targeted collection of data subsets.We propose an algebra called AW-RA and an equivalent pictorial language called aggregation workflows. Aggregation workflows allow for intuitive expression of composite measure queries, and the underlying algebra is designed to facilitate efficient multiscan execution. We describe an evaluation framework based on multiple passes of sorting and scanning over the original dataset. In each pass, several measures are evaluated simultaneously, and dependencies between these measures and containment relationships between the underlying subsets of data are orchestrated to reduce the memory footprint of the computation. We present a performance evaluation that demonstrates the benefits of our approach.