Precision preview-based stable-inversion for nonlinear nonminimum-phase systems: The VTOL example

This article quantifies the importance of the future desired trajectory in determining the exact-output-tracking input for nonlinear, nonminimum-phase systems by using system inversion techniques. It is intuitive that the effect of the desired output's distant-future values, on the output-tracking input at the current time instant, should be small. Therefore, at a current time instant (t_c), preview information of the desired output in a finite-time window [t_c,t_c+T_p] should be sufficient to compute the output-tracking input with an arbitrarily small prescribed error, if the preview time T_p is sufficiently large. The contribution of this article is the quantification of the needed preview time T_p by using the benchmark VTOL aircraft model as an example. Additionally, simulation results are presented to evaluate the efficacy of the finite-preview-based stable-inversion approach.     

On single-walk parallelization of the job shop problem solving algorithms

New parallel objective function determination methods for the job shop scheduling problem are proposed in this paper, considering makespan and the sum of jobs execution times criteria, however, the methods proposed can be applied also to another popular objective functions such as jobs tardiness or flow time. Parallel Random Access Machine (PRAM) model is applied for the theoretical analysis of algorithm efficiency. The methods need a fine-grained parallelization, therefore the approach proposed is especially devoted to parallel computing systems with fast shared memory (e.g. GPGPU, General-Purpose computing on Graphics Processing Units).     

Job scheduling to minimize expected weighted flowtime on uniform processors

We consider a sequencing problem in which there are n jobs to be processed nonpreemptively on m nonidentical processors. The processing time of the j-th processor is exponentially distributed with rate μ_j, where μ₁μ₂μ_m. Job i incurs a holding cost at rate c_i per unit time while still in the system, where c₁c₂c_n. We show that to minimize total expected holding costs (weighted flowtime), it is optimal to take the fastest (lowest indexed) available processor, say processor j, and assign job k to it if k>(Σ_i^j−₁μ_i)/μ_j−j k−1. After each assignment the jobs are renumbered (so that job k+1 becomes job k, etc.), and the procedure is repeated with the next fastest available processor, etc. Note that the policy does not depend on the values of the holding costs c_i. This result is a generalization of the result of Agrawala et al. (1984) for minimizing expected flowtime, i.e., minimizing total holding cost when the holding costs of all the jobs are the same. We give a simpler proof of the more general result.     

A Model for Minimizing Active Processor Time

We introduce the following elementary scheduling problem. We are given a collection of n jobs, where each job J _i has an integer length ? _i as well as a set T _i of time intervals in which it can be feasibly scheduled. Given a parameter B, the processor can schedule up to B jobs at a timeslot t so long as it is “active” at t. The goal is to schedule all the jobs in the fewest number of active timeslots. The machine consumes a fixed amount of energy per active timeslot, regardless of the number of jobs scheduled in that slot (as long as the number of jobs is non-zero). In other words, subject to ? _i units of each job i being scheduled in its feasible region and at each slot at most B jobs being scheduled, we are interested in minimizing the total time during which the machine is active. We present a linear time algorithm for the case where jobs are unit length and each T _i is a single interval, assuming that jobs are given in sorted order. For general T _i , we show that the problem is NP-complete even for B=3. However when B=2, we show that it can be efficiently solved. In addition, we consider a version of the problem where jobs have arbitrary lengths and can be preempted at any point in time. For general B, the problem can be solved by linear programming. For B=2, the problem amounts to finding a triangle-free 2-matching on a special graph. We extend the algorithm of Babenko et al. (Proceedings of the 16th Annual International Conference on Computing and Combinatorics, pp. 120–129, 2010) to handle our variant, and also to handle non-unit length jobs. This yields an \(O(\sqrt{L} m)\) time algorithm to solve the preemptive scheduling problem for B=2, where L=∑ _i ? _i . We also show that for B=2 and unit length jobs, the optimal non-preemptive schedule has active time at most 4/3 times that of the optimal preemptive schedule; this bound extends to several versions of the problem when jobs have arbitrary length.     

Minimizing cycle time and group scheduling, using Petri nets a study of heuristic methods

The objective of this paper is a study of minimizing the maximum completion time min F _max, or cycle time of the last job of a given family of jobs using flow shop heuristic scheduling techniques. Three methods are presented: minimize idle time (MIT); Campbell, Dudek and Smith (CDS); and Palmer. An example problem with ten jobs and five machines is used to compare results of these methods. A deterministic t-timed colored Petri net model has been developed for scheduling problem. An execution of the deterministic timed Petri net allows to compute performance measures by applying graph traversing algorithms starting from initial global state and going into a desirable final state(s) of the production system. The objective of the job scheduling policy is minimizing the cycle time of the last job scheduled in the pipeline of a given family of jobs. Three heuristic scheduling methods have been implemented. First, a sub-optimal sequence of jobs to be scheduled is generated. Second, a Petri net-based simulator with graphical user interface to monitor execution of the sequence of tasks on machines is dynamically designed. A deterministic t-timed colored Petri net model has been developed and implemented for flexible manufacturing systems (FMS). An execution of the deterministic timed Petri net into a reachability graph allows to compute performance measures by applying graph traversing algorithms starting from initial global state to a desirable final state(s) of the production system.     

Performance bound analysis of a heuristic for the total weighted flowtime problem with fixed delivery dates

We consider single-machine scheduling with fixed delivery dates, which are given or determined before the jobs are processed. A job is delivered on the earliest fixed delivery date that is no earlier than its completion time. The flowtime of a job is defined as its delivery date. The objective is to minimize the total weighted flowtime of the jobs. The largest ratio first (LRF) rule is a heuristic that sequences jobs in nonincreasing order of w_j/p_j, where p_j and w_j are the processing time and weight of job J_j, respectively. We investigate the performance bounds of the LRF heuristic under different scenarios of the problem. We conducted computational experiments to test the performance of the heuristic. The results show that the LRF heuristic is able to produce near-optimal and optimal solutions.     

Complexity Results for Single-Machine Problems with Positive Finish-Start Time-Lags

In a single-machine problem with time-lags a set of jobs has to be processed on a single machine in such a way that certain timing restrictions between the finishing and starting times of the jobs are satisfied and a given objective function is minimized. We consider the case of positive finish-start time-lags which mean that between the finishing time of job i and the starting time of job j the minimal distance has to be respected. New complexity results are derived for single-machine problems with constant positive time-lags which also lead to new results for flow-shop problems with unit processing times and job precedences. Received: May 13, 1998; revised November 23, 1998     

Robust Algorithms for Preemptive Scheduling

Preemptive scheduling problems on parallel machines are classic problems. Given the goal of minimizing the makespan, they are polynomially solvable even for the most general model of unrelated machines. In these problems, a set of jobs is to be assigned to run on a set of m machines. A job can be split into parts arbitrarily and these parts are to be assigned to time slots on the machines without parallelism, that is, for every job, at most one of its parts can be processed at each time. Motivated by sensitivity analysis and online algorithms, we investigate the problem of designing robust algorithms for constructing preemptive schedules. Robust algorithms receive one piece of input at a time. They may change a small portion of the solution as an additional part of the input is revealed. The capacity of change is based on the size of the new piece of input. For scheduling problems, the supremum ratio between the total size of the jobs (or parts of jobs) which may be re-scheduled upon the arrival of a new job j, and the size of j, is called migration factor. We design a strongly optimal algorithm with the migration factor $1-\frac{1}{m}$ for identical machines. Strongly optimal algorithms avoid idle time and create solutions where the (non-increasingly) sorted vector of completion times of the machines is lexicographically minimal. In the case of identical machines this results not only in makespan minimization, but the created solution is also optimal with respect to any ? _p norm (for p>1). We show that an algorithm of a smaller migration factor cannot be optimal with respect to makespan or any other ? _p norm, thus the result is best possible in this sense as well. We further show that neither uniformly related machines nor identical machines with restricted assignment admit an optimal algorithm with a constant migration factor. This lower bound holds both for makespan minimization and for any ? _p norm. Finally, we analyze the case of two machines and show that in this case it is still possible to maintain an optimal schedule with a small migration factor in the cases of two uniformly related machines and two identical machines with restricted assignment.     

Sequencing unreliable jobs on parallel machines

This paper addresses an allocation and sequencing problem motivated by an application in unsupervised automated manufacturing. There are n independent jobs to be processed by one of m machines or units during a finite unsupervised duration or shift. Each job is characterized by a certain success probability p _i , and a reward r _i which is obtained if the job is successfully carried out. When a job fails during processing, the processing unit is blocked, and the jobs subsequently scheduled on that machine are blocked until the end of the unsupervised period. The problem is to assign and sequence the jobs on the machines so that the expected total reward is maximized. This paper presents the following results for this problem and some extensions: (i) a polyhedral characterization for the single machine case, (ii) the proof that the problem is NP-hard even with 2 machines, (iii) approximation results for a round-robin heuristic, (iv) an effective upper bound. Extensive computational results show the effectiveness of the heuristic and the bound on a large sample of instances.     

Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs

Motivated by applications in batch scheduling of jobs in manufacturing systems and distributed computing, we study two related problems. Given is a set of jobs {J ₁,…,J _n }, where J _j has a processing time p _j , and an undirected intersection graph G=({1,…,n},E), with an edge (i,j) whenever the pair of jobs J _i and J _j cannot be processed in the same batch. We are to schedule the jobs in batches, where each batch completes its processing when the last job in the batch completes execution. The goal is to minimize the sum of job completion times. Our two problems differ in the definition of completion time of a job within a given batch. In the first variant, a job completes its execution when its batch is completed, whereas in the second variant, a job completes execution when its own processing is completed. For the first variant, we show that an adaptation of the greedy set cover algorithm gives a 4-approximation for perfect graphs. For the second variant, we give new or improved approximations for a number of different classes of graphs. The algorithms are of widely different genres (LP, greedy, subgraph covering), yet they curiously share a common feature in their use of randomized geometric partitioning.     

A DP algorithm for minimizing makespan and total completion time on a series-batching machine

This paper studies a bicriteria scheduling problem on a series-batching machine with objective of minimizing makespan and total completion time simultaneously. A series-batching machine is a machine that can handle up to b jobs in a batch and the completion time of all jobs in a batch is equal to the finishing time of the last job in the batch and the processing time of a batch is the sum of the processing times of jobs in the batch. In addition, there is a constant setup time s for each batch. For the problem we can find all Pareto optimal solutions in O(n²) time by a dynamic programming algorithm, where n denotes the number of jobs.     

Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines

We consider the problem of scheduling a maximum profit selection of equal length jobs on m   identical machines. Jobs arrive online over time and the goal is to determine a non-preemptive schedule which maximizes the total profit of the scheduled jobs. Let the common processing requirement of the jobs be p>0$p>0$. For each job j_i, i=1,…,n we are given a release time r_i (at which the job becomes known) and a deadline _ri+p+_δi$r_i+p+{\delta }_i$. If the job is scheduled and completed before the deadline, a profit of w_i is earned.     

Optimal interval scheduling with a resource constraint

We consider a scheduling problem where n jobs have to be carried out by m parallel identical machines. The attributes of a job j are a fixed start time s_j, a fixed finish time f_j, a resource requirement r_j, and a value v_j. Every machine owns R units of a renewable resource necessary to carry out jobs. A machine can process more than one job at a time, provided the resource consumption does not exceed R. The jobs must be processed in a non-preemptive way. Within this setting, we ask for a subset of jobs that can be feasibly scheduled with the maximum total value. For this strongly NP-hard problem, we first discuss an approximation result. Then, we propose a column generation scheme for the exact solution. Finally, we suggest some greedy heuristics and a restricted enumeration heuristic. All proposed algorithms are implemented and tested on a large set of randomly generated instances. It turns out that the column generation technique clearly outperforms the direct resolution of a natural compact formulation; the greedy algorithms produce good quality solutions in negligible time, whereas the restricted enumeration averages the performance of the greedy methods and the exact technique.     

A Subgradient Descent Algorithm for Optimization of Initially Controllable Flow Shop Systems

We consider an optimization problem for deterministic flow shop systems processing identical jobs. The service times are initially controllable; they can only be set before processing the first job, and cannot be altered between processes. We derive some waiting and completion time characteristics for fixed service time flow shop systems, independent of the cost formulation. Exploiting these characteristics, an equivalent convex optimization problem, which is non-differentiable, is derived along with its subgradient descent solution algorithm. This algorithm not only eliminates the need for convex programming solvers but also allows for the solution of larger systems due to its smaller memory requirements. Significant improvements in solution times are also observed in the numerical examples.

Scalable 2D Convex Hull and Triangulation Algorithms for Coarse Grained Multicomputers

In this paper we describe scalable parallel algorithms for building the convex hull and a triangulation ofncoplanar points. These algorithms are designed for thecoarse grained multicomputermodel:pprocessors withO(n/p)⪢O(1) local memory each, connected to some arbitrary interconnection network. They scale over a large range of values ofnandp, assuming only thatn⩾p^1+ε(ε>0) and require timeO((T_sequential/p)+T_s(n, p)), whereT_s(n, p) refers to the time of a global sort ofndata on approcessor machine. Furthermore, they involve only a constant number of global communication rounds. Since computing either 2D convex hull or triangulation requires timeT_sequential=Θ(n log n) these algorithms either run in optimal time,Θ((n log n)/p), or in sort time,T_s(n, p), for the interconnection network in question. These results become optimal whenT_sequential/pdominatesT_s(n, p) or for interconnection networks like the mesh for which optimal sorting algorithms exist.     

Online scheduling of bounded length jobs to maximize throughput

We consider an online scheduling problem, motivated by the issues present at the joints of networks using ATM and TCP/IP. Namely, IP packets have to be broken down into small ATM cells and sent out before their deadlines, but cells corresponding to different packets can be interwoven. More formally, we consider the online scheduling problem with preemptions, where each job j is revealed at release time r _j , and has processing time p _j , deadline?d _j , and weight w _j . A?preempted job can be resumed at any time. The goal is to maximize the total weight of all jobs completed on time. Our main results are as follows. Firstly, we prove that when the processing times of all jobs are at most k, the optimum deterministic competitive ratio is ??(k/log?k). Secondly, we give a deterministic algorithm with competitive ratio depending on the ratio between the smallest and the largest processing time of all jobs. In particular, it attains competitive ratio 5 in the case when all jobs have identical processing times, for which we give a lower bound of 2.598. The latter upper bound also yields an O(log?k)-competitive randomized algorithm for the variant with processing times bounded by k.     

Optimal state-free, size-aware dispatching for heterogeneous -type systems

We consider a cluster of heterogeneous servers, modeled as M/G/1 first-come first-serve queues with different processing speeds. A dispatcher that assigns jobs to the servers takes as input only the size of the arriving job and the overall job-size distribution. This general model captures the behavior of a variety of real systems, such as web server clusters. Our goal is to identify assignment strategies that the dispatcher can perform to minimize expected completion time and waiting time. We show that there exist optimal strategies that are deterministic, fixing the server to which jobs of particular sizes are always sent. We prove that the optimal strategy for systems with identical servers assigns a non-overlapping interval range of job sizes to each server. We then prove that when server processing speeds differ, it is necessary to assign each server a distinct set of intervals of job sizes in order to minimize expected waiting or response times.     

Periodic input estimation for linear periodic systems: Automotive engine applications

In this paper, we consider periodic linear systems driven by T₀-periodic signals that we desire to reconstruct. The systems under consideration are of the form , y=C(t)x, x∈Rⁿ, w∈R^m, y∈R^p, (m?p?n) where A(t), A₀(t), and C(t) are T₀-periodic matrices. The period T₀ is known. The T₀-periodic input signal w(t) is unknown but is assumed to admit a finite dimensional Fourier decomposition. Our contribution is a technique to estimate w from the measurements y. In both full state measurement and partial state measurement cases, we propose an efficient observer for the coefficients of the Fourier decomposition of w(t). The proposed techniques are particularly attractive for automotive engine applications where sampling time is short. In this situation, standard estimation techniques based on Kalman filters are often discarded (because of their relative high computational burden). Relevance of our approach is supported by two practical cases of application. Detailed convergence analysis is also provided. Under standard observability conditions, we prove asymptotic convergence when the tuning parameters are chosen sufficiently small.     

Maximizing the throughput of parallel jobs on hypercubes

We study a problem of scheduling n independent parallel jobs on hypercubes. A parallel job is required to be scheduled on a subcube of processors. All jobs are available at the beginning, each of which is associated with a due date. The objective is to maximize the total number of early jobs. We provide an optimal polynomial time algorithm for the unit processing time job system.     

Three-machine flowshop with two operations per job to minimize makespan

This work studies three variants of a three-machine flowshop problem with two operations per job to minimize makespan (F3/o = 2/C_max). A set of n jobs are classified into three mutually exclusive families A, B and C. The families A, B and C are defined as the set of jobs that is scheduled in machine sequence (M₁, M₂), (M₁, M₃) and (M₁, M₃), respectively, where (M_x, M_y) specifies the machine sequence for the job that is processed first on M_x, and then on M_y. Specifically, jobs with the same route (machine sequence) are classified into the same family. Three variants of F3/o = 2/C_max are studied. First, F3/GT, no-idle, o = 2/C_max, in which both machine no-idle and GT restrictions are considered. The GT assumption requires that all jobs in the same family are processed contiguously on the machine and the machine no-idle assumption requires that all machines work continuously without idle time. Second, the problem F3/GT, o = 2/C_max, in which the machine no-idle restriction in the first variant is relaxed, is considered. Third, the problem F3/no-idle, o = 2/C_max with the GT assumption in the first variant relaxed is considered. Based on the dominance conditions developed, the optimal solution is polynomially derived for each variant. These results may narrow down the gap between easy and hard cases of the general problem.