Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects

In this paper we consider the single machine past-sequence-dependent (p-s-d) setup times scheduling problems with general position-dependent and time-dependent learning effects. By the general position-dependent and time-dependent learning effects, we mean that the actual processing time of a job is not only a function of the total normal processing times of the jobs already processed, but also a function of the job’s scheduled position. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the θth (θ ? 0) power of job completion times, the total lateness, the total weighted completion time, the maximum lateness, the maximum tardiness and the number of tardy jobs. We show that the problems of makespan, the total completion time, the sum of the θth (θ ? 0) power of job completion times and the total lateness can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem, the maximum lateness minimization problem, maximum tardiness minimization problem and the number of tardy jobs minimization problem can be solved in polynomial time under certain conditions.     

Parallel machine scheduling with a convex resource consumption function

We consider some problems of scheduling jobs on identical parallel machines where job-processing times are controllable through the allocation of a nonrenewable common limited resource. The objective is to assign the jobs to the machines, to sequence the jobs on each machine and to allocate the resource so that the makespan or the sum of completion times is minimized. The optimization is done for both preemptive and nonpreemptive jobs. For the makespan problem with nonpreemptive jobs we apply the equivalent load method in order to allocate the resources, and thereby reduce the problem to a combinatorial one. The reduced problem is shown to be NP-hard. If preemptive jobs are allowed, the makespan problem is shown to be solvable in O(n²) time. Some special cases of this problem with precedence constraints are presented and the problem of minimizing the sum of completion times is shown to be solvable in O(n log n) time.     

On “P” property and the column-W property

P-matrices play an important role in the well-posedness of a linear complementarity problem (LCP). Similarly, the well-posedness of a horizontal linear complementarity problem (HLCP) is closely related to the column-W property of a matrix k-tuple.In this paper we first consider the problem of generating P-matrices from a given pair of matrices. Given a matrix pair (D, F) where D is a square matrix of order m and matrix F has m rows, “what are the conditions under which there exists a matrix G such that (D + FG) is a P-matrix?”. We obtain necessary and sufficient conditions for the special case when the column rank of F is m ? 1. A decision algorithm of complexity O(m²) to check whether the given pair of matrices (D, F) is P-matrisable is obtained. We also obtain a necessary and an independent sufficient condition for the general case when rank(F) is less than m ? 1.We then generalise the P-matrix generating problem to the generation of matrix k-tuples satisfying the column-W property from a given matrix (k + 1)-tuple. That is, given a matrix (k + 1)-tuple (D₁, … ,D_k, F), where D_js are square matrices of order m and F is a matrix having m rows, we determine the conditions under which the matrix k-tuple (D₁ + FG₁, … ,D_k + FG_k) satisfies the column-W property. As in the case of P-matrices we obtain necessary and sufficient conditions for the case when rank(F) = m ? 1. Using these conditions a decision algorithm of complexity O(km²) to check whether the given matrix (k + 1)-tuple is column-W matrisable is obtained. Then for the case when rank(F) is less than m ? 1, we obtain a necessary and an independent sufficient condition.For a special sub-class of P-matrices we give a polynomial time decision algorithm for P-matrisability. Finally, we obtain a geometric characterisation of column-W property by generalising the well known separation theorem for P-matrices.     

A note on the flow time and the number of tardy jobs in stochastic open shops

In this note open shops with two machines are considered. The processing time of job j, j = 1, …, n, on machine 1 (2) is a random variable X_j (Y_j), which is exponentially distributed with rate γ (μ). If the completion time of job j is C_j, a waiting cost is incurred of g(C_j), where g is a function that is increasing concave. The preemptive policy that minimizes the total expected waiting cost E(Σg(C_j)) is determined. Two machine open shops with jobs that have random due dates are considered as well. For the case where the due dates D₁,…,D_n are exchangeable, the preemptive policy that minimizes the expected number of tardy jobs is determined.     

Multi-server machine repair problems under a (V, R) synchronous single vacation policy

This paper considers a machine repair problem with M operating machines and S standbys, in which R repairmen are responsible for supervising these machines and operate a (V, R) vacation policy. With such policy, if the number of the failed machines is reduced to R − V (R > V) (there exists V idle repairmen) at a service completion, these V idle servers will together take a synchronous vacation (or leave for other secondary job). Upon returning from the vacation, they do not take a vacation again and remain idle until the first arriving failed machine arrives. The steady-state probabilities are solved in terms of matrix forms and the system performance measures are obtained. Algorithmic procedures are provided to deal with the optimization problem of discrete/continuous decision variables while maintaining a minimum specified level of system availability.     

Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures

Suppose that there are n jobs and n machines and it costs c_ij to execute job i on machine j. The assignment problem concerns the determination of a one‐to‐one assignment of jobs onto machines so as to minimize the cost of executing all the jobs. When the c_ij are independent and identically distributed exponentials of mean 1, Parisi [Technical Report cond‐mat/9801176, xxx LANL Archive, 1998] made the beautiful conjecture that the expected cost of the minimum assignment equals . Coppersmith and Sorkin [Random Structures Algorithms 15 ( 6 ), 113–144] generalized Parisi's conjecture to the average value of the smallest k‐assignment when there are n jobs and m machines. Building on the previous work of Sharma and Prabhakar [Proc 40th Annu Allerton Conf Communication Control and Computing, 20 , 657–666] and Nair [Proc 40th Annu Allerton Conf Communication Control and Computing, 17 , 667–673], we resolve the Parisi and Coppersmith‐Sorkin conjectures. In the process we obtain a number of combinatorial results which may be of general interest.© 2005 Wiley Periodicals, Inc. Random Struct. Alg. 2005     

Approximation schemes for parallel machine scheduling with availability constraints

We investigate the problems of scheduling n weighted jobs to m parallel machines with availability constraints. We consider two different models of availability constraints: the preventive model, in which the unavailability is due to preventive machine maintenance, and the fixed job model, in which the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that m is a constant, and that the jobs are non-resumable.For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even if w_i=p_i for all jobs. In this paper, we assume that there is one machine that is permanently available and that the processing time of each job is equal to its weight for all jobs. We develop the first polynomial-time approximation scheme (PTAS) when there is a constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, and thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; and (2) to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Next, we show that there is no fully polynomial-time approximation scheme (FPTAS) in this case unless P=NP.For the fixed job model, it has been shown that if job weights are arbitrary then there is no constant approximation for a single machine with 2 fixed jobs or for two machines with one fixed job on each machine, unless P=NP. In this paper, we assume that the weight of a job is the same as its processing time for all jobs. We show that the PTAS for the preventive model can be extended to solve this problem when the number of fixed jobs and the number of machines are both constants.     

An exact algorithm for the knapsack sharing problem with common items

We are concerned with a variation of the knapsack problem as well as of the knapsack sharing problem, where we are given a set of n items and a knapsack of a fixed capacity. As usual, each item is associated with its profit and weight, and the problem is to determine the subset of items to be packed into the knapsack. However, in the problem there are s players and the items are divided into s + 1 disjoint groups, N_k (k = 0, 1, … , s). The player k is concerned only with the items in N₀ ∪ N_k, where N₀ is the set of ‘common’ items, while N_k represents the set of his own items. The problem is to maximize the minimum of the profits of all the players. An algorithm is developed to solve this problem to optimality, and through a series of computational experiments, we evaluate the performance of the developed algorithm.     

Online cardinality constrained scheduling

In online load balancing problems, jobs arrive over a list. Upon arrival of a job, the algorithm is required to assign it immediately and irrevocably to a machine. We consider such a makespan minimization problem with an additional cardinality constraint, i.e., at most k jobs may be assigned to each machine, where k is a parameter of the problem. We present both upper and lower bounds on the competitive ratio of online algorithms for this problem with identical machines.     

An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines

We give a new and efficient approximation algorithm for scheduling precedence-constrained jobs on machines with different speeds. The problem is as follows. We are given n jobs to be scheduled on a set of m machines. Jobs have processing times and machines have speeds. It takes p_j/s_i units of time for machine i with speed s_i to process job j with processing requirement p_j. Precedence constraints between jobs are given in the form of a partial order. If j k, processing of job k cannot start until job j's execution is completed. The objective is to find a non-preemptive schedule to minimize the makespan of the schedule. Chudak and Shmoys (1997, “Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),” pp. 581–590) gave an algorithm with an approximation ratio of O(log m), significantly improving the earlier ratio of due to Jaffe (1980, Theoret. Comput. Sci.26, 1–17). Their algorithm is based on solving a linear programming relaxation. Building on some of their ideas, we present a combinatorial algorithm that achieves a similar approximation ratio but runs in O(n³) time. Our algorithm is based on a new and simple lower bound which we believe is of independent interest.     

Parallel machine scheduling with nested processing set restrictions

We consider the problem of scheduling a set of n independent jobs on m parallel machines, where each job can only be scheduled on a subset of machines called its processing set. The machines are linearly ordered, and the processing set of job j   is given by two machine indexes _aj$a_j$ and _bj$b_j$; i.e., job j   can only be scheduled on machines _aj,_aj+1,…,_bj$a_j\text{,}{a}_j+1\text{,}\dots \text{,}{b}_j$. Two distinct processing sets are either nested or disjoint. Preemption is not allowed. Our goal is to minimize the makespan. It is known that the problem is strongly NP-hard and that there is a list-type algorithm with a worst-case bound of 2-1/m$2-1/m$. In this paper we give an improved algorithm with a worst-case bound of 7/4. For two and three machines, the algorithm gives a better worst-case bound of 5/4 and 3/2, respectively.     

A graph-theoretic approach to interval scheduling on dedicated unrelated parallel machines

We study the problem of scheduling n non-preemptive jobs on m unrelated parallel machines. Each machine can process a specified subset of the jobs. If a job is assigned to a machine, then it occupies a specified time interval on the machine. Each assignment of a job to a machine yields a value. The objective is to find a subset of the jobs and their feasible assignments to the machines such that the total value is maximized. The problem is NP-hard in the strong sense. We reduce the problem to finding a maximum weight clique in a graph and survey available solution methods. Furthermore, based on the peculiar properties of graphs, we propose an exact solution algorithm and five heuristics. We conduct computer experiments to assess the performance of our and other existing heuristics. The computational results show that our heuristics outperform the existing heuristics.     

A semi-Markov process with an inverse Gaussian distribution as sojourn time

Let X_n denote the state of a device after n repairs. We assume that the time between two repairs is the time τ taken by a Wiener process {W(t), t ? 0}, starting from w₀ and with drift μ < 0, to reach c ∈ [0, w₀). After the nth repair, the process takes on either the value X_n?1 + 1 or X_n?1 + 2. The probability that X_n = X_n?1 + j, for j = 1, 2, depends on whether τ ? t₀ (a fixed constant) or τ > t₀. The device is considered to be worn out when X_n ? k, where k ∈ {1, 2, …}. This model is based on the ones proposed by Rishel (1991) [1] and Tseng and Peng (2007) [2]. We obtain an explicit expression for the mean lifetime of the device. Numerical methods are used to illustrate the analytical findings.     

Iterated greedy local search methods for unrelated parallel machine scheduling

This work deals with the parallel machine scheduling problem which consists in the assignment of n jobs on m   parallel machines. The most general variant of this problem is when the processing time depends on the machine to which each job is assigned to. This case is known as the unrelated parallel machine problem. Similarly to most of the literature, this paper deals with the minimization of the maximum completion time of the jobs, commonly referred to as makespan (_Cmax)$(C_{\text{max}})$. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated procedures. By contrast, in this paper we propose a set of simple iterated greedy local search based metaheuristics that produce solutions of very good quality in a very short amount of time. Extensive computational campaigns show that these solutions are, most of the time, better than the current state-of-the-art methodologies by a statistically significant margin.     

Competitive online scheduling of perfectly malleable jobs with setup times

We study how to efficiently schedule online perfectly malleable parallel jobs with arbitrary arrival times on m ? 2 processors. We take into account both the linear speedup of such jobs and their setup time, i.e., the time to create, dispatch, and destroy multiple processes. Specifically, we define the execution time of a job with length p_j running on k_j processors to be p_j/k_j + (k_j − 1)c, where c > 0 is a constant setup time associated with each processor that is used to parallelize the computation. This formulation accurately models data parallelism in scientific computations and realistically asserts a relationship between job length and the maximum useful degree of parallelism. When the goal is to minimize makespan, we show that the online algorithm that simply assigns k_j so that the execution time of each job is minimized and starts jobs as early as possible has competitive ratio 4(m − 1)/m for even m ? 2 and 4m/(m + 1) for odd m ? 3. This algorithm is much simpler than previous offline algorithms for scheduling malleable jobs that require more than a constant number of passes through the job list.     

1D numerical simulation of charge trapping in an insulator submitted to an electron beam irradiation. Part I: Computation of the initial secondary electron emission yield

The aim of this work is to study by numerical simulation a mathematical modelling technique describing charge trapping during initial charge injection in an insulator submitted to electron beam irradiation. A two-fluxes method described by a set of two stationary transport equations is used to split the electron current j_e(z) into coupled forward j_e+(z) and backward j_e?(z) currents and such that j_e(z) = j_e+(z) ? j_e?(z). The sparse algebraic linear system, resulting from the vertex-centered finite-volume discretization scheme is solved by an iterative decoupled fixed point method which involves the direct inversion of a bi-diagonal matrix.The sensitivity of the initial secondary electron emission yield with respect to the energy of incident primary electrons beam, that is penetration depth of the incident beam, or electron cross sections (absorption and diffusion) is investigated by numerical simulations.     

Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds

We present new approximation algorithms for the problem of scheduling precedence-constrained jobs on parallel machines that are uniformly related. That is, there arenjobs andmmachines; each jobjrequiresp_junits of processing, and is to be processed on one machine without interruption; if it is assigned to machinei, which runs at a given speeds_i, it takesp_j/s_itime units. There also is a partial order on the jobs, wherej kimplies that jobkmay not start processing until jobjhas been completed. We consider two objective functions:C_max = max_j C_j, whereC_jdenotes the completion time of jobj, and ∑_jw_jC_j, wherew_jis a weight that is given for each jobj. For the first objective, the best previously known result is an -approximation algorithm, which was shown by Jaffe more than 15 years ago. We give anO(log m)-approximation algorithm. We also show how to extend this result to obtain anO(log m)-approximation algorithm for the second objective, albeit with a somewhat larger constant. These results also extend to settings in which each jobjhas a release dater_jbefore which the job may not begin processing. In addition, we obtain stronger performance guarantees if there are a limited number of distinct speeds. Our results are based on a new linear programming-based technique for estimating the speed at which each job should be run, and a variant of the list scheduling algorithm of Graham that can exploit this additional information.     

Backtracking and its Amoebic Properties in One-dimensional Machine Location Problems

This paper studies the assignment of M unique machines to M equally spaced locations along a linear material handling track with the objective of minimizing the cost of (jobs) backtracking (i.e. moving upstream). Because of the arrangement of machines and restrictions imposed by the sequence of operations for each job, some jobs may have to backtrack to complete required processing on different machines. This problem is formulated as a quadratic assignment problem. An optimal solution to a problem with large M is computationally intractable. The backtracking distance matrix in problems involving equally-spaced machine locations in one dimension is seen to possess some unique characteristics called amoebic properties. Ten amoebic properties have been identified and exploited to devise a heuristic and a lower bound on the optimal solution. Results which describe the performance of the heuristic and the lower bound are presented.     

Outsourcing and scheduling for two-machine ordered flow shop scheduling problems

This paper considers a two-machine ordered flow shop problem, where each job is processed through the in-house system or outsourced to a subcontractor. For in-house jobs, a schedule is constructed and its performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and the total outsourcing cost. Since this problem is NP-hard, we present an approximation algorithm. Furthermore, we consider three special cases in which job j has a processing time requirement p_j, and machine i a characteristic q_i. The first case assumes the time job j occupies machine i is equal to the processing requirement divided by a characteristic value of machine i, that is, p_j/q_i. The second (third) case assumes that the time job j occupies machine i is equal to the maximum (minimum) of its processing requirement and a characteristic value of the machine, that is, max{p_j, q_i} (min{p_j, q_i}). We show that the first and the second cases are NP-hard and the third case is polynomially solvable.