Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines

We give a polynomial approximation scheme for the problem of scheduling on uniformly related parallel machines for a large class of objective functions that depend only on the machine completion times, including minimizing the l_p norm of the vector of completion times. This generalizes and simplifies many previous results in this area.     

提前/延期惩罚最小化互替机床调度算法

对经提前/延期（E/T）惩罚最小为目标的互替机床调度问题进行了分析,对互替机床E/T调度问题进行了描述,提出了解决调度问题的具体策略,在此基础上,建立了基于启发式的互替机床E/T调度算法,最后通过仿真实验验证了本算法的有效性和实用性。     

Optimal preemptive semi-online scheduling on two uniform processors

We investigate a preemptive semi-online scheduling problem. Jobs with sizes within a certain range [1,r] (r?1) arrive one by one to be scheduled on two uniform parallel processors with speed 1 and s?1, respectively. The objective is to minimize makespan. We characterize the optimal competitive ratio as a function of both s and r by devising a deterministic on-line scheduling algorithm along with a matching lower bound, which also holds for randomized algorithms.     

Optimal On-Line Algorithms to Minimize Makespan on Two Machines with Resource Augmentation

We study the problem of on-line scheduling on two uniformly related machines where the on-line algorithm has resources different from those of the off-line algorithm. We consider three versions of this problem, preemptive semi-online, non-preemptive on-line and preemptive on-line scheduling. For all these cases we design algorithms with best possible competitive ratios as functions of the machine speeds. This work was submitted as a part of the M.Sc. thesis of the second author. A preliminary version of this paper appeared in the proceedings of The First Workshop on Approximation and Online Algorithms (WAOA’03), pages 109–122.     

Minimizing total weighted completion time when scheduling orders in a flexible environment with uniform machines

We consider the scheduling of orders in an environment with m uniform machines in parallel. Each order requests certain amounts of k different product types. Each product type can be produced by any one of the m machines. No setup is required if a machine switches over from one product type to another. Different product types intended for the same order can be produced at the same time (concurrently) on different machines. Each order is released at time zero and has a positive weight. Preemptions are allowed. The completion time of an order is the finish time of the product type that is completed last for that order. The objective is to minimize the total weighted completion time. We propose heuristics for the non-preemptive as well as the preemptive case and obtain worst case bounds that are a function of the number of machines as well as the differences in the speeds of the machines. Even though the worst-case bounds we showed for the two heuristics are not very tight, our experimental results show that they yield solutions that are very close to optimal.     

Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard

One of the first problems to be studied in scheduling theory was the problem of minimizing the makespan in a two-machine flow shop. Johnson showed that this problem can be solved in O(n log n) time. A crucial assumption here is that the time needed to move a job from the first to the second machine is negligible. If this is not the case and if this delay is not equal for all jobs, then the problem becomes NP-hard in the strong sense. We show that this is even the case if all processing times are equal to one. As a consequence, we show strong NP-hardness of a number of similar problems, including a severely restricted version of the Numerical 3-Dimensional Matching problem.     

A note on “An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs”

We point out an error in the algorithm for the Load Balanced Semi-Matching Problem presented by C.P. Low [C.P. Low, An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs, Information Processing Letters 100 (2006) 154-161]. This problem is equivalent to a parallel machine scheduling problem subject to eligibility constraints, in which each job has a pre-determined set of machines capable of processing the job.     

A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families

We consider the problem of minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals. We propose a family of iterative improvement heuristics based on previous work by Potts [Analysis of a heuristic for one machine sequencing with release dates and delivery times. Operations Research 1980;28:1436–41] and Uzsoy [Scheduling batch processing machines with incompatible job families. International Journal for Production Research 1995;33(10):2685–708] and combine them with a genetic algorithm (GA) based on the random keys encoding of Bean [Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing 1994;6(2):154–60]. Extensive computational experiments show that one of the proposed GAs runs significantly faster than the other, providing a good tradeoff between solution time and quality. The combination of iterative heuristics with GAs consistently outperforms the iterative heuristics on their own.     

Block models for scheduling jobs on two parallel machines with a single server

We consider the problem of scheduling a set of non-preemptable jobs on two identical parallel machines such that the makespan is minimized. Before processing, each job must be loaded on a machine, which takes a given setup time. All these setups have to be done by a single server which can handle at most one job at a time. For this problem, we propose a mixed integer linear programming formulation based on the idea of decomposing a schedule into a set of blocks. We compare the results obtained by the model suggested with known heuristics from the literature.     

Minimizing resource consumption on uniform parallel machines with a bound on makespan

With the crucial issue of environmental protection, managing natural resources efficiently and/or reducing the amount of carbon emissions have become more important than ever. In this paper, we introduce a uniform parallel machine scheduling problem where the objective is to minimize resource consumption given that the maximum completion time does not exceed a certain level. We show that the problem is strongly NP-hard. A tight lower bound and a particle swarm optimization algorithm are then developed. Finally, some computational results are provided.     

Worst-case analysis of LPT scheduling on a small number of non-identical processors

The approximation ratio of the longest processing time (LPT) scheduling algorithm has been investigated in various studies. While the tight approximation ratio is known for the cases when all processors are identical, the ratio is unknown when the processors have different speeds. In this study, we provide a tight approximation ratio for three, four, and five processors. We show that the ratios for these cases are no larger than the lower bound provided by Gonzalez et al. (1977) [14]. The ratios are approximately 1.38, 1.43, and 1.46 for three, four, and five processors, respectively.     

A branch-and-price algorithm for the general case of scheduling parallel machines with a single server

We consider the strongly NP-hard problem of scheduling two-operation non-preemptable jobs on two identical parallel machines. A single server, that can handle at most one job at a time, is available to carry out the first (or setup) operation. The second operation, to be carried out on the same machine but without the server, must be executed immediately after the setup. The objective is to minimize the makespan. We apply a column generation method to a population of partial schedules, in turn generated by some well known heuristics, to achieve effective and efficient solutions. We compare the performance of this method with those proposed earlier and also suggest future work.     

Minimizing the number of tardy jobs on a proportionate flowshop with general position-dependent processing times

In various real life scheduling systems job processing times vary according to the number of jobs previously processed. The vast majority of studies assume a restrictive functional form to describe job processing times. In this note, we address a scheduling problem with the most general job processing time functions. The machine setting assumed is an m-machine proportionate flowshop, and the objective function is minimum number of tardy jobs. We show that the problem can be formulated as a bottleneck assignment problem with a maximum cardinality constraint. An efficient polynomial time (O(n⁴ log n)) solution is introduced.     

Parallel machine scheduling problem with preemptive jobs and transportation delay

In this research the parallel machine scheduling problem with preemption by considering a constant transportation delay for migrated jobs and minimization of makespan as the criterion i.e., P_m|pmtn(delay)|C_max is investigated. It is assumed that when a preempted job resumes on another machine, it is required a delay between the processing time of the job on these two machines. This delay is called transportation delay. We criticize an existing mathematical model for the research problem in the literature [Boudhar M, Haned A. Preemptive scheduling in the presence of transportation times. Computers & Operations Research 2009; 36(8):2387–93]. Then, we prove that there exists an optimal schedule with at most (m−1) preemptions with transportation among machines for the problem. We also propose a linear programming formulation and an exact algorithm for the research problem in case of equal transportation delay. The experiments show that the proposed exact algorithm performs better than the proposed mathematical model.     

The Complexity of Parallel Multisearch on Coarse-Grained Machines

Given m ordered segments that form a partition of some universe (e.g., a two-dimensional strip), the multisearch problem consists of determining, for a set of n query points in the universe, the segments they belong to. We present the first nontrivial parallel deterministic scheme for performing multisearch on a distributed-memory machine when m=ω(n) . The scheme is designed on the BSP* model of parallel computation, a variant of Valiant's BSP which rewards blockwise communication, and relies on a suitable redundant representation of the segments. The time needed to answer the queries is analyzed as a function of the redundancy and of the BSP* parameters. We show that optimal performance can be obtained using logarithmic redundancy. We also prove a lower bound on the communication requirements of any deterministic multisearch scheme realized on a distributed-memory machine. The lower bound exhibits a tradeoff between the redundancy used to represent the segments and the performance of the scheme. Received June 1, 1997; revised March 10, 1998.     

Preemptive Scheduling on Uniform Parallel Machines with Controllable Job Processing Times

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.     

Notes on Max Flow Time Minimization with Controllable Processing Times

In a scheduling problem with controllable processing times the job processing time can be compressed through incurring an additional cost. We consider the identical parallel machines max flow time minimization problem with controllable processing times. We address the preemptive and non-preemptive version of the problem. For the preemptive case, a linear programming formulation is presented which solves the problem optimally in polynomial time. For the non-preemptive problem it is shown that the First In First Out (FIFO) heuristic has a tight worst-case performance of 3–2/m, when jobs processing times and costs are set as in some optimal preemptive schedule. Supported by Swiss National Science Foundation project 20-63733.00/1, Resource Allocation and Scheduling in Flexible Manufacturing Systems, and by the Metaheuristics Network, grant HPRN-CT-1999-00106.     

Scheduling jobs with equal processing times and time windows on identical parallel machines

We present a linear programming approach to the problem of scheduling equal processing time jobs with release dates and deadlines on identical parallel machines. The known algorithm with complexity O(n ³log log n) of B. Simons schedules all the jobs while minimizing both the maximum completion time and the mean flow time. Our approach permits also to minimize the weighted sum of completion times and total tardiness in polynomial time for the problems without deadlines. The complexity status of these problems was open. Contract/grant sponsor: Alexander von Humboldt Foundation.     

Total absolute deviation of job completion times on uniform and unrelated machines

Unlike other measures of variation of job completion times considered in scheduling literature, the measure of minimizing total absolute deviation of job completiontimes (TADC) was shown to have a polynomial time solution on a single machine. It was recently shown to remain polynomially solvable when position-dependent job processing times are assumed. In this paper we further extend these results, and show that minimizing TADC remains polynomial when position-dependent processing times are assumed (i) on uniform and unrelated machines and (ii) for a bicriteria objective consisting of a linear combination of total job completion times and TADC. These extensions are shown to be valid also for the measure of total absolute differences of job waiting times (TADW).