A projective algorithm for preemptive open shop scheduling with two multiprocessor groups

We study a multiprocessor extension of the preemptive open shop scheduling problem, where the set of processors is partitioned into processor groups. We show that the makespan minimization problem is polynomially solvable for two multiprocessor groups even if preemptions are restricted to integral times.     

Algorithms for some graph theoretical optimization problems

This is a summary of the main results presented in the author’s PhD thesis. This thesis, written in English, was supervised by Frits Spieksma and defended on September 23, 2005 at the Katholieke Universiteit Leuven. A copy of the thesis is available from the authors website (http://www.econ. kuleuven.be/linda.moonen/public/). The thesis can be roughly split into two parts. The first part is dedicated to the problem of partitioning partially ordered sets into chains of limited size. The second part deals with the structure and the connectivity of the Internet.     

Minimizing the number of machines for scheduling jobs with equal processing times

In this paper, we consider a parallel machine environment when all jobs have the same processing time and arbitrary release dates and deadlines of the jobs are given. We suppose that the available number of machines, which can be used simultaneously, may vary over time. The aim is to construct a feasible schedule in such a way that the maximal number of simultaneously used machines is minimal. We give a polynomial algorithm for this problem.     

Homomorphism-Homogeneous Partially Ordered Sets

A structure is called homogeneous if every isomorphism between finite substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron and J. Nešetřil introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finite substructures of the structure extends to an endomorphism of the structure. In this paper we characterize homomorphism-homogeneous partially ordered sets (where a homomorphism between partially ordered sets A and B is a mapping f : A →B satisfying ). We show that there are five types of homomorphism-homogeneous partially ordered sets: partially ordered sets whose connected components are chains; trees; dual trees; partially ordered sets which split into a tree and a dual tree; and X ₅-dense locally bounded partially ordered sets. Supported by the Ministry od Science and Environmental Protection of the Republic of Serbia, Grant No. 144017.     

An extension of set partitioning with application to scheduling problems

The well known problems of set covering, set partitioning and set packing are defined and their interrelationship is considered. A natural generalisation called the extended set partitioning model is presented and the three standard models are shown to be special cases of this generalisation. In addition, the extended model includes another type of set problem which can be of greater use in certain applications. The model forms the basis of a computer assisted bus crew scheduling system developed by the authors. The system is in regular use by Dublin City Services in the Republic of Ireland. Finally, the equivalence between a special case of the set partitioning problem and the shortest route problem is considered and it is shown that this equivalence also applies to the extended model.     

Optimal preemptive scheduling on a fixed number of identical parallel machines

In this paper, we consider the preemptive scheduling problem on a fixed number of identical parallel machines. We present a polynomial-time algorithm for finding a minimal length schedule for an order class which contains properly interval orders.     

Irreducible Width 2 Posets of Linear Discrepancy 3

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x) − h _L (y)| ≤ k, where h _L (x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width 2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique linear extension that witnesses linear discrepancy 2. The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290.     

Multiprocessor scheduling: combining LPT and MULTIFIT

We consider the problem of scheduling a set of n independent jobs on m identical machines with the objective of minimizing the total finishing time. We combine the two most popular algorithms, LTP and MULTIFIT, to form a new one. MULTIFIT is well known to have better error bound than LPT with the price paid in running time. Although MULTIFIT provides a better error bound, in many cases LPT still can yield better results. This motivates the development of this new combined algorithm, which uses the result of LPT as the incumbent and then applies MULTIFIT with fewer iterations. The performance of this combined algorithm is better than that of LPT because it uses LPT as an incumbent. The error bound of this combined algorithm is never worse than that of MULTIFIT. For example, the error bound of implementing this combined algorithm to the two-processor problem is , compared to the error bound of in MULTIFIT. Empirical results of the comparison for schedules obtained by the combined algorithm, MULTIFIT and LPT are also provided.     

Preemptive scheduling with staircase and piecewise linear resource availability

Some variations are presented for the preemptive scheduling problem on unrelated processors, one shows how nonrenewable resources with a time-varying supply may be taken into account in an extension of the two-phase method; phase 1 consists in solving an LP problem and phase 2 is the construction of the schedule; such a construction reduces to the determination of integral vectors in polyhedra defined by totally unimodular matrices. In special cases, this is simply a compatible flow problem.

---

Zusammenfassung Es werden Variationen für Reihenfolgeprobleme mit Unterbrechungen betrachtet bei denen die Aufgaben mit unterschiedlicher Bearbeitungszeit auf den einzelnen Maschinen gelöst werden können. Insbesondere wird ein Problem mit nichterneuerbaren Resourcen und zeitabhängigen Nachfragen behandelt und es wird gezeigt, daß dieses Problem durch eine Erweiterung der 2-Phasenmethode gelöst werden kann. In Phase 1 wird ein LP gelöst, während in Phase 2 ein zugehöriger Schedule konstruiert wird. Diese Konstruktion erfolgt durch die Bestimmung ganzzahliger Vektoren, die Ecken eines Polyeders entsprechen, der durch eine vollständig unimodulare Matrix definiert wird. In Spezialfällen reduziert sich dies auf Flußprobleme.

     

Dynamic multi-appointment patient scheduling for radiation therapy

Seeking to reduce the potential impact of delays on radiation therapy cancer patients such as psychological distress, deterioration in quality of life and decreased cancer control and survival, and motivated by inefficiencies in the use of expensive resources, we undertook a study of scheduling practices at the British Columbia Cancer Agency (BCCA). As a result, we formulated and solved a discounted infinite-horizon Markov decision process for scheduling cancer treatments in radiation therapy units. The main purpose of this model is to identify good policies for allocating available treatment capacity to incoming demand, while reducing wait times in a cost-effective manner. We use an affine architecture to approximate the value function in our formulation and solve an equivalent linear programming model through column generation to obtain an approximate optimal policy for this problem. The benefits from the proposed method are evaluated by simulating its performance for a practical example based on data provided by the BCCA.     

Preemptive scheduling of equal-length jobs to maximize weighted throughput

We study the problem of computing a preemptive schedule of equal-length jobs with given release times, deadlines and weights. Our goal is to maximize the weighted throughput. In Graham's notation this problem is described as . We provide an O(n⁴)-time algorithm, improving the previous bound of O(n¹⁰).     

Some branch and bound techniques for nonlinear optimization

The range of nonlinear optimization problems which can be solved by Linear Programming and the Branch and Bound algorithm is extended by introducing Chains of Linked Ordered Sets and by allowing automatic interpolation of new variables. However this approach involves solving a succession of linear subproblems, whose solutions in general violate the logical requirements of the nonlinear formulation and may lie far from any local or global optimum. The paper describes techniques which are designed to improve the performance of the Branch and Bound algorithm on problems containing chains, and which also yield benefits in integer programming.Each linear subproblem is tightened towards the corresponding nonlinear problem by removing variables which must logically be nonbasic in any feasible solution. This is achieved by a presolve procedure, and also by post-optimal Lagrangian relaxation which tightens the bound on the objective function by assessing the cheapest way to satisfy any violated chain constraints. Frequently fewer subsequent branches are required to find a feasible solution or to prove infeasibility.Formerly of Scicon Ltd.     

Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements

We consider the resource-constrained scheduling problem when each job’s resource requirements remain constant over its processing time. We study a time-indexed formulation of the problem, providing facet-defining inequalities for a projection of the resulting polyhedron that exploit the resource limitations inherent in the problem. Lifting procedures are then provided for obtaining strong valid inequalities for the original polyhedron. Computational results are presented to demonstrate the strength of these inequalities.     

The fractional weak discrepancy of a partially ordered set

In this paper we introduce the notion of the fractional weak discrepancy of a poset, building on previous work on weak discrepancy in [J.G. Gimbel and A.N. Trenk, On the weakness of an ordered set, SIAM J. Discrete Math. 11 (1998) 655-663; P.J. Tanenbaum, A.N. Trenk, P.C. Fishburn, Linear discrepancy and weak discrepancy of partially ordered sets, ORDER 18 (2001) 201-225; A.N. Trenk, On k-weak orders: recognition and a tolerance result, Discrete Math. 181 (1998) 223-237]. The fractional weak discrepancywd_F(P) of a poset P=(V,?) is the minimum nonnegative k for which there exists a function f:V→R satisfying (1) if a?b then f(a)+1?f(b) and (2) if a∥b then |f(a)-f(b)|?k. We formulate the fractional weak discrepancy problem as a linear program and show how its solution can also be used to calculate the (integral) weak discrepancy. We interpret the dual linear program as a circulation problem in a related directed graph and use this to give a structural characterization of the fractional weak discrepancy of a poset.     

Graph models for scheduling systems with machine saturation property

Let be a set of n independent tasks and a set of m processors. During each time instant, each processor can be used by a single task at most. A schedule is for each task an allocation of one or more time intervals to one or more processors. A schedule is said to be optimal if it minimizes the maximum completion time. We say a schedule S has the machine saturation property (MS property) if, at any time instant of task execution, all the machines are simultaneously busy. In this paper, we analyze the conditions under which a parallel scheduling system allows a schedule with the MS property. While for some simple models the analytical conditions can be easily stated, a graph model approach is required when conflicts of processor usage are present. For this reason, we define the class of saturated graphs that correspond to scheduling systems with the MS property. We present efficient graph recognition algorithms to verify the MS property directly on some classes of saturated graphs     

具有等级约束的三台机排序问题的可中断在线算法

研究具有等级约束的三台机在线排序问题．机器和工件的等级数均为1或2,工件只能在等级数不超过自身等级的机器上加工,且加工允许中断,目标是极小化最大工件完工时间．如果有两台机器等级为1,给出竞争比为3／2的在线算法,并证明算法是最好可能的;如果只有一台等级为1的机器,也给出竞争比为3／2的在线算法．     

Hierarchies of Partially Ordered Connectives and Quantifiers

Connections between partially ordered connectives and Henkin quantifiers are considered. It is proved that the logic with all partially ordered connectives and the logic with all Henkin quantifiers coincide. This implies that the hierarchy of partially ordered connectives is strongly hierarchical and gives several nondefinability results between some of them. It is also deduced that each Henkin quantifier can be defined by a quantifier of the form what is a strengthening of the Walkoe result. MSC: 03C80.     

Asymptotic scheduling

We deal with the following scheduling problem: a finite set of jobs is given and each job consists in the execution of an infinite number of tasks. A task is a sequence of operations and each operation requires a specific machine. A machine can process only one operation at a time and preemption is not allowed. Performance measures of the processing system involve fixing a time horizon T, counting the number of tasks completed within T for each job and maximizing a specified function of these numbers to estimate the throughput of the schedule. Whilst computing the throughput for a given T is in general an extremely difficult problem, it is shown in this paper that the limit, as T tends to infinity, of the average throughput (i.e. the throughput divided by T) can be easily computed via Linear Programming under fairly mild conditions. This quantity, which may be called the asymptotic throughput, can be used to assess a bound on performance measures of real systems. Buffers play a crucial role and buffer sizes can be taken care of in assessing the system performance. Mathematics Subject Classification (2000):90B35, 90C05, 90C27, 90C90     

Preemptive multiprocessor order scheduling to minimize total weighted flowtime

Consider m identical machines in parallel, each of which can produce k different product types. There is no setup cost when the machines switch from producing one product type to another. There are n orders each of which requests various quantities of the different product types. All orders are available for processing at time t = 0, and preemption is allowed. Order i has a weight w_i and its completion time is the time when its last requested product type finishes. Our goal is to find a preemptive schedule such that the total weighted completion time ∑_wiCi$\sum w_i{C}_i$ is minimized. We show that this problem is NP-hard even when all jobs have identical weights and there are only two machines. Motivated by the computational complexity of the problem, we propose a simple heuristic and show that it obeys a worst-case bound of 2 − 1/m. Finally, empirical studies show that our heuristic performs very well when compared with a lower bound of the optimal cost.