Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε$2+\epsilon$.     

Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time

We are interested in the problem of scheduling orders for different product types in a facility with a number of machines in parallel. Each order asks for certain amounts of various different product types which can be produced concurrently. Each product type can be produced on a subset of the machines. Two extreme cases of machine environments are of interest. In the first case, each product type can be produced on one and only one machine which is dedicated to that product type. In the second case, all machines are identical and flexible; each product type can be produced by any one of the machines. Moreover, when a machine in this case switches over from one product type to another, no setup is required. Each order has a release date and a weight. Preemptions are not allowed. The objective is minimizing the total weighted completion time of the orders. Even when all orders are available at time 0, both types of machine environments have been shown to be NP-hard for any fixed number (≥2) of machines. This paper focuses on the design and analysis of approximation algorithms for these two machine environments. We also present empirical comparisons of the various algorithms. The conclusions from the empirical analyses provide insights into the trade-offs with regard to solution quality, speed, and memory space. Electronic Supplementary Material The online version of this article () contains supplementary material, which is available to authorized users. This research is supported by the National Science Foundation through grants DMI-0300156 and DMI-0245603.     

Non-identical parallel-machine scheduling research with minimizing total weighted completion times: Models,relaxations and algorithms

We consider a class of non-identical parallel-machine scheduling problems in which the goal is to minimize total (or mean) weighted (or unweighted) completion time. Models and relaxations are collected and classified in this paper. Heuristics and optimizing techniques are surveyed for the problems. And a few of interesting areas for future research are also provided.     

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.     

NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time

Baker and Nuttle [K.R. Baker, H.L.W. Nuttle, Sequencing independent jobs with a single resource, Naval Research Logistics Quarterly 27 (1980) 499–510] studied the following single-variable-resource scheduling problem: sequencing n jobs for processing by a single resource to minimize a function of job completion times, when the availability of the resource varies over time. When the objective function to be minimized is the total weighted completion time, Baker and Nuttle conjectured that the problem is NP-hard. We show in this note that the conjecture is true.     

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.     

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.     

A memetic algorithm for minimizing the total weighted completion time on a single machine under linear deterioration

In this paper, we consider the problem of minimizing the total weighted completion time on a single machine. Jobs processing times are increasing linear function of start times. First, we present some new dominance properties for this NP-hard problem. And next, using these properties, we develop a memetic algorithm for the problem. The results of computational experiments show the good performance of the proposed algorithm.     

Performance of scheduling algorithms for no-wait flowshops with parallel machines

We study the performance of scheduling algorithms for a manufacturing system, called the ‘no-wait flowshop’, which consists of a certain number of machine centers. Each center has one or more identical parallel machines. Each job is processed by at most one machine in each center. The problem of finding the minimum finish time schedule is considered here in a flowshop consisting of two machine centers. Heuristic algorithms are presented and are analyzed in the worst case performance context. For the case of two centers, one with a single machine and the other with m, two heuristics are presented with tight performance guarantees of 3 − (1/m) and 2. When both centers have m machines, a heuristic is presented with an upper bound performance guarantee of . It is also shown that this bound can be reduced to 2(1 + ε). For the flowshop with any number of machines in each center, we provide a heuristic algorithm with an upper bound performance guarantee that depends on the relative number of machines in the centers.     

关于Atiyah-Singer指标定理的随机方法证明

运用随机分析中的广义Wiener泛函给出Atiyah-Singer指标定理的新的随机方法的证明, 这一证明在形式上是比较自然简单的. 广义Wiener泛函由Watanabe (1989, 1990) 建立和运用.     

Complexity of a scheduling problem with controllable processing times

We consider the problem of scheduling a set of independent jobs on a single machine so as to minimize the total weighted completion time, subject to the constraint that the total compression cost is less than or equal to a fixed amount. The complexity of this problem is mentioned as an open problem. In this note we show that the problem is NP-hard.     

On the effectiveness of the Harmonic Shelf Algorithm for on-line strip packing

In [J. Csirik, G.J. Woeginger, An on-line algorithm for multidimensional bin packing, Inform. Process. Lett. 63 (1997) 171-175] the authors study the asymptotic worst case ratio between the height of the strip needed to on-line pack a list of boxes by means of the Harmonic Shelf Algorithm and the height of the strip used by an optimal algorithm. In this note we analyze the effectiveness of the former algorithm in terms of the ratio between the unused area inside the strip and the total size of this strip, and we show that the Harmonic Shelf Algorithm is also capable of packing items so that the asymptotic worst case value of this ratio comes arbitrarily close to .     

Note on “A note on single-machine group scheduling problems with position-based learning effect”

In a recent paper, Lee and Wu [W.-C. Lee, C.-C. Wu, A note on single-machine group scheduling problems with position-based learning effect, Appl. Math. Model. 33 (2009) 2159–2163] proposed a new group scheduling learning model where the learning effect not only depends on the job position, but also depends on the group position. They investigate the makespan and the total completion time minimization problems on a single-machine. As for the total completion time minimization problem, they assumed that the numbers of jobs in each group are the same and the group normal setup and the job normal processing times are agreeable. Under the assumption conditions, they showed that the total completion time minimization problem can be optimally solved in polynomial time solution. However, the assumption conditions for the total completion time minimization problem do not reflect actual practice in many manufacturing processes. Hence, in this note, we propose other agreeable conditions and show that the total completion time minimization problem remains polynomially solvable under the agreeable conditions.     

A new heuristic for open shop total completion time problem

The m  -machine open shop problem to minimize the sum of the completion times is investigated in our paper. First, a heuristic algorithm, Shortest Processing Time Block, is presented to deal with problem _Om|n=km|∑_Cj$O_m|n=\mathit{km}|\sum C_j$, where k   is positive integer. And then, the heuristic is extended to solve the general problem _Om‖∑_Cj$O_m\Vert \sum C_j$. It is proved that the heuristic is asymptotically optimal when the job number goes to infinity. At the end of this paper, numerical experimentation results show the effectiveness of the heuristic algorithm.     

Fast approximation algorithms for bi-criteria scheduling with machine assignment costs

We consider parallel machine scheduling problems where the processing of the jobs on the machines involves two types of objectives. The first type is one of two classical objective functions in scheduling theory: either the total completion time or the makespan. The second type involves an actual cost associated with the processing of a specific job on a given machine; each job-machine combination may have a different cost. Two bi-criteria scheduling problems are considered: (1) minimize the maximum machine cost subject to the total completion time being at its minimum, and (2) minimize the total machine cost subject to the makespan being at its minimum. Since both problems are strongly NP-hard, we propose fast heuristics and establish their worst-case performance bounds.