Solving similarity joins and range queries in metric spaces with the list of twin clusters

The metric space model abstracts many proximity or similarity problems, where the most frequently considered primitives are range and k-nearest neighbor search, leaving out the similarity join, an extremely important primitive. In fact, despite the great attention that this primitive has received in traditional and even multidimensional databases, little has been done for general metric databases.We solve two variants of the similarity join problem: (1) range joins: Given two sets of objects and a distance threshold r, find all the object pairs (one from each set) at distance at most r; and (2) k-closest pair joins: Find the k closest object pairs (one from each set). For this sake, we devise a new metric index, coined List of Twin Clusters (LTC), which indexes both sets jointly, instead of the natural approach of indexing one or both sets independently. Finally, we show how to use the LTC in order to solve classical range queries. Our results show significant speedups over the basic quadratic-time naive alternative for both join variants, and that the LTC is competitive with the original list of clusters when solving range queries. Furthermore, we show that our technique has a great potential for improvements.     

Scheduling products with subassemblies and changeover time

We revisit the problem, previously studied by Coffman et al, of scheduling products with two subassemblies on a common resource, where changeovers consume time, under the objective of flow-time minimization. We derive some previously unidentified structural properties that could be important to researchers working on similar batch scheduling problems. We show that there exists a series of base schedules from which optimal schedules can be easily derived. As these base schedules build on each other, they are easy to construct as well. We also show that the structure of these base schedules is such that batch sizes decrease over time in a well-defined manner. These insights about the general form of the schedules might also be important to practitioners wanting some intuition about the schedule structure that they are implementing.     

A Common Error in Production Scheduling

Many production scheduling systems use schedules of planned start/finish times for jobs up to a given planning horizon which includes the period between rescheduling operations. The integrity and usefulness of such schedules depends on the accuracy of the estimated time data which is available on the operations to be performed.There is a widespread belief that "on the average" if errors in the estimated time data are not biased then they will balance out and the schedules will give a reasonable plan for the period between rescheduling operations. This paper uses the elementary theory of the simple random walk to show that this assumption is not valid and that scheduling systems based upon it will not make sufficient allowance for the relatively highly probable events of permanent under-schedule or over-schedule conditions.     

Estimating disk head movement in batched searching

The study considers the problem of evaluating the expected disk head movement when the SCAN disk scheduling policy is used to answer a batch of queries. The two cases examined are: (a) the batched queries are based on primary key values, and (b) each query in the batch is based on secondary key values.Earlier works assumed that hit cylinders are non-distinct and derived an exact (approximate) formula for the first (second) case. In this paper, both replacement and non-replacement models are examined and new exact (exact and approximate) formulae are derived for the first (second) case. It is shown that earlier and new approximate results may be used instead of the computationally expensive exact formulae.     

Bicriteria scheduling for contiguous and non contiguous parallel tasks

We study the problem of scheduling on k identical machines a set of parallel tasks with release dates and deadlines in order to maximize simultaneously two criteria, namely the Size (number of scheduled tasks) and the Weight (sum of the weights of scheduled tasks). If no task requires more than half of the machines, we construct schedules that are simultaneously approximations for the Size and the Weight by combining two approximate schedules, one for each parameter. We obtain existence results and polynomial time bicriteria approximation algorithms in contiguous and non contiguous models.     

Clinic scheduling models with overbooking for patients with heterogeneous no-show probabilities

Clinical overbooking is intended to reduce the negative impact of patient no-shows on clinic operations and performance. In this paper, we study the clinical scheduling problem with overbooking for heterogeneous patients, i.e. patients who have different no-show probabilities. We consider the objective of maximizing expected profit, which includes revenue from patients and costs associated with patient waiting times and physician overtime. We show that the objective function with homogeneous patients, i.e. patients with the same no-show probability, is multimodular. We also show that this property does not hold when patients are heterogeneous. We identify properties of an optimal schedule with heterogeneous patients and propose a local search algorithm to find local optimal schedules. Then, we extend our results to sequential scheduling and propose two sequential scheduling procedures. Finally, we perform a set of numerical experiments and provide managerial insights for health care practitioners.     

Minimizing the overhead for some tree-scheduling problems

This paper is devoted to the study of tree-scheduling problems within the execution model described by Anderson, Beame and Ruzzo. We first prove the NP-completeness of the problem of minimizing the overhead for scheduling trees on m processors, and then we propose an algorithm that provides optimal schedules when complete trees are considered.     

Evaluating the impact of operating conditions on the performance of appointment scheduling rules in service systems

The general practice in implementing an appointment scheduling rule (ASR) is to enforce a certain rule, such as “block appointment”, to schedule customer arrivals in service systems. The operating environments of service systems are expected to affect considerably the performance of a selected ASR. The objective of this paper is to evaluate the impact of the environmental factors which include probability of no-show (ρ), the coefficient of variation (C_ν) of service times, and the number of customers per service session (N). The extent to which a certain environmental factor affects the performance of ASR is examined to see if there is any ASR that performs well under most operating conditions. Under situations characterized by 27 different combinations of the factors ρ, C_ν, and N, the performance of nine scheduling rules are evaluated by a simulation study. The simulation results show that an ASR designed to reduce customer waiting time performs very well in most operating environments considered. One commonly used ASR in real-world service systems, which schedules several customers to arrive at the start of each service session, tends to induce long customer waiting time.     

带有运输且加工具有灵活性的无等待流水作业排序问题

研究一类带有运输且加工具有灵活性的两阶段无等待流水作业排序问题, 其中每阶段只有一台机器, 每个工件有两道工序需要依次在两台机器上加工, 工件在两台机器上的加工及两道工序之间不允许等待. 给出两种近似算法, 并分别分析其最坏情况界. 第一种算法是排列排序, 证明了最坏情况界不超过5/2; 第二种算法将工件按照两道工序加工时间之和的递增顺序排序, 证明其最坏情况界不超过2. 最后, 通过数值模拟比较算法的性能. 对问题中各参数取不同值的情况, 分别生成若干个实例, 用算法得到的解与最优解的下界作比值, 通过分析这些比值的最大值、最小值和平均值来比较上述两个算法的性能.     

Structural properties of optimal schedules with preemption

Scheduling problems with preemption are considered, where each operation can be interrupted and resumed later without any penalty. We investigate some basic properties of their optimal solutions. When does an optimal schedule exist (provided that there are feasible schedules)? When does it have a finite/polynomial number of interruptions? Do they occur at integral/rational points only? These theoretical questions are also of practical interest, since structural properties can be used to reduce the search space in a practical scheduling application. In this paper we answer some of these basic questions for a rather general scheduling model (including, as the special cases, the classicalmodels such as parallelmachine scheduling, shop scheduling, and resource constrained project scheduling) and for a large variety of the objective functions including nearly all known. For some two special cases of objective functions (including, however, all classical ones), we prove the existence of an optimal solution with a special “rational structure.” An important consequence of this property is that the decision versions of these optimization scheduling problems belong to class NP.     

An improved lower bound for a bi-criteria scheduling problem

For the bi-criteria scheduling problem of minimizing the sum of completion times and the sum of weighted completion times, min-sum of weighted completion times, we prove that there exists no constant β>1 such that (1+1/γ,β)-approximate schedules can be found for any γ>0. This result confirms a recently published conjecture.     

Rollout Algorithms for Stochastic Scheduling Problems

Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.     

Scheduling with release dates and preemption to minimize multiple max-form objective functions

In this paper, we study multi-agent scheduling with release dates and preemption on a single machine, where the scheduling objective function of each agent to be minimized is regular and of the maximum form (max-form). The multi-agent aspect has three versions, namely ND-agent (multiple agents with non-disjoint job sets), ID-agent (multiple agents with an identical job set), and CO-agent (multiple competing agents with mutually disjoint job sets). We consider three types of problems: The first type (type-1) is the constrained scheduling problem, in which one objective function is to be minimized, subject to the restriction that the values of the other objective functions are upper bounded. The second type (type-2) is the weighted-sum scheduling problem, in which a positive combination of the objective functions is to be minimized. The third type (type-3) is the Pareto scheduling problem, for which we aim to find all the Pareto-optimal points and their corresponding Pareto-optimal schedules. We show that the type-1 problems are polynomially solvable, and the type-2 and type-3 problems are strongly NP-hard even when all jobs’ release dates are zero and processing times are one. When the number of the scheduling criteria is fixed and they are all lateness-like, such as minimizing C_max, F_max, L_max, T_max, and WC_max, where WC_max is the maximum weighted completion time of the jobs, the type-2 and type-3 problems are polynomially solvable. To address the type-3 problems, we develop a new solution technique that guesses the Pareto-optimal points through some elaborately constructed schedule-configurations.     

Scheduling CCRR tournaments

In this paper, we construct CCRRS, complete coupling round robin schedules, for n teams each consisting of two pairs. The motivation for these schedules is a problem in scheduling bridge tournaments. We construct CCRRS(n) for n a positive integer, n?3, with the possible exceptions of n∈{54,62}. For n odd, we show that a CCRRS(n) can be constructed using a house with a special property. For n even, a CCRRS(n) can be constructed from a Howell design, H(2n-2,2n), with a special property called Property P. We use a combination of direct and recursive constructions to construct H(2n-2,2n) with Property P. In order to apply our main recursive construction, we need group divisible designs with odd group sizes and odd block sizes. One of our main results is the existence of these group divisible designs.     

Optimisation of fault-tolerant fabric-cutting schedules using genetic algorithms and fuzzy set theory

In apparel industry, manufacturers developed standard allowed minutes (SAMs) databases on various manufacturing operations in order to facilitate better scheduling, while effective production schedules ensure smoothness of downstream operations. As apparel manufacturing environment is fuzzy and dynamic, rigid production schedules based on SAMs become futile in the presence of any uncertainty. In this paper, a fuzzification scheme is proposed to fuzzify the static standard time so as to incorporate some uncertainties, in terms of both job-specific and human related factors, into the fabric-cutting scheduling problem. A genetic optimisation procedure is also proposed to search for fault-tolerant schedules using genetic algorithms, such that makespan and scheduling uncertainties are minimised. Two sets of real production data were collected to validate the proposed method. Experimental results indicate that the genetically optimised fault-tolerant schedules not only improve the operation performance but also minimise the scheduling risks.     

On polynomial solvability of two multiprocessor scheduling problems

We discuss a new approach for solving multiprocessor scheduling problems by using and improving results for guillotine pallet loading problem. We introduce a new class of schedules by analogy with the guillotine restriction for cutting stock problem and show that many well-known algorithms from classical scheduling theory construct schedules only from this class. We also consider two multiprocessor scheduling problems and prove that they can be solved in polynomial time.     

A polyhedral approach to single-machine scheduling problems

We report new results for a time-indexed formulation of nonpreemptive single-machine scheduling problems. We give complete characterizations of all facet inducing inequalities with integral coefficients and right-hand side 1 or 2 for the convex hull of the set of feasible partial schedules, i.e., schedules in which not all jobs have to be started. Furthermore, we identify conditions under which these facet inducing inequalities are also facet inducing for the original polytope, which is the convex hull of the set of feasible complete schedules, i.e., schedules in which all jobs have to be started. To obtain insight in the effectiveness of these classes of facet-inducing inequalities, we develop a branch-and-cut algorithm based on them. We evaluate its performance on the strongly NP-hard single machine scheduling problem of minimizing the weighted sum of the job completion times subject to release dates. Received March 24, 1994 / Revised version received February 13, 1997 Published online June 28, 1999     

Flow-level performance and capacity of wireless networks with user mobility

The performance evaluation of wireless networks is severely complicated by the specific features of radio communication, such as highly variable channel conditions, interference issues, and possible hand-offs among base stations. The latter elements have no natural counterparts in wireline scenarios, and create a need for novel performance models that account for the impact of these characteristics on the service rates of users. Motivated by the above issues, we review several models for characterizing the capacity and evaluating the flow-level performance of wireless networks carrying elastic data transfers. We first examine the flow-level performance and stability of a wide family of so-called α-fair channel-aware scheduling strategies. We establish that these disciplines provide maximum stability, and describe how the special case of the Proportional Fair policy gives rise to a Processor-Sharing model with a state-dependent service rate. Next we turn attention to a network of several base stations with inter-cell interference. We derive both necessary and sufficient stability conditions and construct lower and upper bounds for the flow-level performance measures. Lastly we investigate the impact of user mobility that occurs on a slow timescale and causes possible hand-offs of active sessions. We show that the mobility tends to increase the capacity region, both in the case of globally optimal scheduling and local α-fair scheduling. It is additionally demonstrated that the capacity and user throughput improve with lower values of the fairness index α.     

Power-aware scheduling of preemptable jobs on identical parallel processors to minimize makespan

This paper deals with power-aware scheduling of preemptable jobs on identical parallel processors to minimize schedule length when jobs are described by continuous, strictly concave functions relating their processing speed at time t to the amount of power allotted at the moment. Power is a continuous, doubly constrained resource, i.e. both: its availability at time t and consumption over scheduling horizon are constrained. Precedence constraints among jobs are represented by a task-on-arc graph. A methodology based on properties of optimal schedules is presented for solving the problem optimally for a given ordering of nodes in the graph. Heuristics for finding an ordering which leads to possibly short schedules are proposed and examined experimentally.     

A two-stage solution approach for personalized multi-department multi-day shift scheduling

In this paper, we address a personalized multi-department multi-day shift scheduling problem with a multi-skill heterogeneous workforce where employees can be transferred between departments under some restrictions. The objective is to construct a schedule that minimizes under-coverage, over-coverage, transfer and labor costs. We propose a novel two-stage approach to solve it: the first stage considers an approximate and smaller problem based on data aggregation and produces approximate transfers. The second stage constructs personalized schedules based on the information deduced from the first stage. An exhaustive experimental study is conducted and proves the efficiency of the proposed approach in terms of solution quality and computing times.