Minimizing total weighted flow time under uncertainty using dominance and a stability box

We consider an uncertain single-machine scheduling problem, in which the processing time of a job can take any real value on a given closed interval. The criterion is to minimize the total weighted flow time of the n jobs, where there is a weight associated with a job. We calculate a number of minimal dominant sets of the job permutations (a minimal dominant set contains at least one optimal permutation for each possible scenario). We introduce a new stability measure of a job permutation (a stability box) and derive an exact formula for the stability box, which runs in O(n log n) time. We investigate properties of a stability box. These properties allow us to develop an O(n²)-algorithm for constructing a permutation with the largest volume of a stability box. If several permutations have the largest volume of a stability box, the developed algorithm selects one of them due to a simple heuristic. The efficiency of the constructed permutation is demonstrated on a large set of randomly generated instances with 10≤n≤1000.     

Exact Largest and Smallest Size of Components

Golomb and Gaal [15] study the number of permutations on n objects with largest cycle length equal to k . They give explicit expressions on ranges n/(i+1) < k ≤ n/i for i=1,2, \ldots, derive a general recurrence for the number of permutations of size n with largest cycle length equal to k , and provide the contribution of the ranges (n/(i+1),n/i] for i=1,2,\ldots, to the expected length of the largest cycle. We view a cycle of a permutation as a component. We provide exact counts for the number of decomposable combinatorial structures with largest and smallest components of a given size. These structures include permutations, polynomials over finite fields, and graphs among many others (in both the labelled and unlabelled cases). The contribution of the ranges (n/(i+1),n/i] for i=1,2,\ldots, to the expected length of the smallest and largest component is also studied. Received June 27, 2000; revised October 8, 2000.     

Fast Generation of Random Permutations Via Networks Simulation

We consider the problem of generating random permutations with uniform distribution. That is, we require that for an arbitrary permutation π of n elements, with probability 1/n! the machine halts with the i th output cell containing π(i) , for 1 ≤ i ≤ n . We study this problem on two models of parallel computations: the CREW PRAM and the EREW PRAM. The main result of the paper is an algorithm for generating random permutations that runs in O(log log n) time and uses O(n ^1+o(1) ) processors on the CREW PRAM. This is the first o(log n) -time CREW PRAM algorithm for this problem. On the EREW PRAM we present a simple algorithm that generates a random permutation in time O(log n) using n processors and O(n) space. This algorithm outperforms each of the previously known algorithms for the exclusive write PRAMs. The common and novel feature of both our algorithms is first to design a suitable random switching network generating a permutation and then to simulate this network on the PRAM model in a fast way. Received November 1996; revised March 1997.     

Parallel permutation generation on linear array

Given n items, a parallel algorithm for generating all the n! permutations is presented. The computational model used is a linear array which consists of n identical processing elements with a simple structure. One permutation is produced at each other time step. The elapsed time to produce a permutation is independent of the integer n. The basic idea used is the iterative method and the exchange of two consecutive components in an existing permutation. The design procedures of this algorithm are considered in detail. The ranking and unranking functions of the required permutations are also discussed.     

Using Metric Spaces in Optimum Scheduling

The solution of an optimum problem of scheduling with n workpieces and m machine tools represents an optimum schedule of putting pieces on machines. In turn, the schedule is defined by an optimum collection of m permutations out of n objects, i.e., the vector permutation = (₁, ..., _m ), where each permutation _i (1 i m) points up the sequence of working of all pieces on the ith machine. In this case, to each admissible schedule there must correspond an integral point from the m-dimensional Euclidean space of permutations (or, which is practically the same, the permutation out of numbers {1, 2, ..., mn}. In an effort to seek an optimum schedule, use is made of the notion of a metric space in the set of admissible schedules and the justified methodology of the search for an optimum schedule. A few metric spaces are described and analyzed and their comparative effectiveness is investigated for the solution of a different-route problem of scheduling.     

An effective neighborhood search algorithm for scheduling a flow shop of batch processing machines

This paper considers scheduling problem of flow shop with many batch processing machines and objective of maximum lateness. An effective neighborhood search algorithm (NSA) is proposed for the problem, in which a job permutation and a batch permutation are used to indicate the solution of two sub-problems, respectively. Each job permutation consists of several family-permutations for the representation of jobs from the same family. Two swaps are applied to two permutations to produce new solutions. NSA is applied to a number of instances and compared with some methods, and computational results validate the good performance of NSA.     

Batching and scheduling in a multi-machine flow shop

We study the problem of batching and scheduling n jobs in a flow shop comprising m, m≥2, machines. Each job has to be processed on machines 1,…,m in this order. Batches are formed on each machine. A machine dependent setup time precedes the processing of each batch. Jobs of the same batch are processed on each machine sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs of the same batch formed on machine l become available for a downstream operation on machine l+1 at the same time when the processing of the last job of the batch on machine l has been finished. The objective is to minimize maximum job completion time. We establish several properties of an optimal schedule and develop polynomial time algorithms for important special cases. They are improvements over the existing methods with regard to their generality and time efficiency.     

Preemptive and Non-preemptive On-line Algorithms for Scheduling with Rejection on Two Uniform Machines

In this paper, we consider the problem of on-line scheduling a job sequence on two uniform machines. A job can be either rejected, in which case we pay its penalty, or scheduled on machines, in which case it contributes its processing time to the makspan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule for all accepted jobs and the penalties of all rejected jobs. Both preemptive and non-preemptive versions are considered. For the preemptive version, we present an optimal on-line algorithm with a competitive ratio for any s≥1, where s is the machine speed ratio. For the non-preemptive version, we present an improved lower bound. Moreover, as an optimal algorithm for s≥1.6180 is known, we present a modified version of the known algorithm, and show that it becomes optimal for any 1.3852≤s<1.6180 and has a smaller competitive ratio than that of original version for any 1≤s<1.3852. The maximum gap between its competitive ratio and the lower bound is 0.0534.     

Efficient Communication Strategies for Ad Hoc Wireless Networks

An ad hoc wireless network is a collection of wireless mobile hosts forming a temporary network without the aid of any established infrastructure or centralized administration. This type of network is of great importance in situations where it is very difficult to provide the necessary infrastructure, but it is a challenging task to enable fast and reliable communication within such a network. In this paper we model and analyze the performance of so-called power-controlled ad hoc wireless networks: networks where the mobile hosts are able to change their transmission power. We concentrate on finding schemes for routing arbitrary permutations in these networks. In general, it is NP-hard even to find an n ^1-ε -approximation for any constant ε to the fastest possible strategy for routing a given permutation problem on n mobile hosts. However, we demonstrate here that if we allow ourselves to consider slightly less general problems, efficient solutions can be found. We first demonstrate that there is a natural class of distributed schemes for handling node-to-node communication on top of which online route selection and scheduling strategies can be constructed such that the performance of this class of schemes can be exploited in a nearly optimal way for routing permutations in any static power-controlled ad hoc network. We then demonstrate that if we restrict ourselves to the important case of routing between nodes distributed randomly in a Euclidean space, we can route in a time that is asymptotically optimal for any routing scheme. Received in final form January 31, 2000. Online publication October 10, 2000.     

A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems

This paper presents a novel discrete differential evolution (DDE) algorithm for solving the no-wait flow shop scheduling problems with makespan and maximum tardiness criteria. First, the individuals in the DDE algorithm are represented as discrete job permutations, and new mutation and crossover operators are developed based on this representation. Second, an elaborate one-to-one selection operator is designed by taking into account the domination status of a trial individual with its counterpart target individual as well as an archive set of the non-dominated solutions found so far. Third, a simple but effective local search algorithm is developed to incorporate into the DDE algorithm to stress the balance between global exploration and local exploitation. In addition, to improve the efficiency of the scheduling algorithm, several speed-up methods are devised to evaluate a job permutation and its whole insert neighborhood as well as to decide the domination status of a solution with the archive set. Computational simulation results based on the well-known benchmarks and statistical performance comparisons are provided. It is shown that the proposed DDE algorithm is superior to a recently published hybrid differential evolution (HDE) algorithm [Qian B, Wang L, Huang DX, Wang WL, Wang X. An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Computers & Operations Research 2009;36(1):209–33] and the well-known multi-objective genetic local search algorithm (IMMOGLS2) [Ishibuchi H, Yoshida I, Murata T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation 2003;7(2):204–23] in terms of searching quality, diversity level, robustness and efficiency. Moreover, the effectiveness of incorporating the local search into the DDE algorithm is also investigated.     

Non-approximability of just-in-time scheduling

We consider the following single machine just-in-time scheduling problem with earliness and tardiness costs: Given n jobs with processing times, due dates and job weights, the task is to schedule these jobs without preemption on a single machine such that the total weighted discrepancy from the given due dates is minimum. NP-hardness of this problem is well established, but no approximation results are known. Using the gap-technique, we show in this paper that the weighted earliness–tardiness scheduling problem and several variants are extremely hard to approximate: If n denotes the number of jobs and b∈ℕ is any given constant, then no polynomial-time algorithm can achieve an approximation which is guaranteed to be at most a factor of O(b ⁿ ) worse than the optimal solution unless P = NP.     

Scheduling unit length jobs on parallel machines with lookahead information

This paper studies two closely related online-list scheduling problems of a set of n jobs with unit processing times on a set of m multipurpose machines. It is assumed that there are k different job types, where each job type can be processed on a unique subset of machines. In the classical definition of online-list scheduling, the scheduler has all the information about the next job to be scheduled in the list while there is uncertainty about all the other jobs in the list not yet scheduled. We extend this classical definition to include lookahead abilities, i.e., at each decision point, in addition to the information about the next job in the list, the scheduler has all the information about the next h jobs beyond the current one in the list. We show that for the problem of minimizing the makespan there exists an optimal (1-competitive) algorithm for the online problem when there are two job types. That is, the online algorithm gives the same minimal makespan as the optimal offline algorithm for any instance of the problem. Furthermore, we show that for more than two job types no such online algorithm exists. We also develop several dynamic programming algorithms to solve a stochastic version of the problem, where the probability distribution of the job types is known and the objective is to minimize the expected makespan.     

置换表示方法求解多卫星多地面站调度问题

针对多卫星成像和多地面站数传并存的对地成像调度问题,从置换空间到调度解空间的映射方法和置换空间的搜索算法两方面进行了研究.提出了一种数传时间窗优先的置换序列映射算法,并证明该映射算法可以将置换序列映射到调度解空间上的最优解.提出了一种遗传随机搜索算法,基于有记忆随机邻域搜索,在置换空间上进行搜索.仿真计算表明,随机邻域搜索可以增强遗传算法的局部搜索能力,搜索结果平均获得了4.64%的改进.     

Some scheduling problems with deteriorating jobs and learning effects

Although scheduling with deteriorating jobs and learning effect has been widely investigated, scheduling research has seldom considered the two phenomena simultaneously. However, job deterioration and learning co-exist in many realistic scheduling situations. In this paper, we introduce a new scheduling model in which both job deterioration and learning exist simultaneously. The actual processing time of a job depends not only on the processing times of the jobs already processed but also on its scheduled position. For the single-machine case, we derive polynomial-time optimal solutions for the problems to minimize makespan and total completion time. In addition, we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain agreeable conditions. For the case of an m-machine permutation flowshop, we present polynomial-time optimal solutions for some special cases of the problems to minimize makespan and total completion time.     

Scheduling jobs with equal processing times subject to machine eligibility constraints

We consider the problem of nonpreemptively scheduling a set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a prespecified set of machines on which it can be processed, called its eligible set. We consider the most general case of machine eligibility constraints as well as special cases of nested and inclusive eligible sets. Both online and offline models are considered. For offline problems we develop optimal algorithms that run in polynomial time, while for online problems we focus on the development of optimal algorithms of a new and more elaborate structure as well as approximation algorithms with good competitive ratios.     

飞机地面作业提前/拖期调度研究

对具有不同时间窗的提前/拖期调度方法应用于飞机地面作业调度进行了研究,用模糊规划建立数学模型,用三角模糊数表示了地面作业中时间的不确定性,应用粒子群优化算法对模型进行了仿真。实验结果表明,在不同情况下该算法都能取得较为满意的结果。     

Modeling and heuristics for scheduling of distributed job shops

This paper deals with the problem of distributed job shop scheduling in which the classical single-facility job shop is extended to the multi-facility one. The mathematical formulation of the problem is comprehensively discussed. Two different mixed integer linear programming models in form of sequence and position based variables are proposed. Using commercial software of CPLEX, the small sized problems are optimally solved. To solve large sized problems, besides adapting three well-known heuristics, three greedy heuristics are developed. The basic idea behind the developed heuristics is to iteratively insert operations (one at each iteration) into a sequence to build up a complete permutation of operations. The permutation scheme, although having several advantages, suffers from redundancy which is having many different permutations representing the same schedule. The issue is analyzed to recognize the redundant permutation. That improves efficiency of heuristics. Comprehensive experiments are conducted to evaluate the performance of the two models and the six heuristics. The results show sequence based model and greedy heuristics equipped with redundancy exclusion are effective for the problem.     

Common Intervals of Multiple Permutations

Given k permutations of n elements, a k-tuple of intervals of these permutations consisting of the same set of elements is called a common interval. We present an algorithm that finds in a family of k permutations of n elements all z common intervals in optimal O(kn+z) time and O(n) additional space. Additionally, we show how to adapt this algorithm to multichromosomal and circular permutations.     

An Optimal Systolic Algorithm for Generating Permutations in Lexicographic Order

A systolic algorithm is described for generating all permutations of n elements in lexicographic order. The algorithm is designed to be executed on a linear array of n processors, each having constant size memory, and each being responsible for producing one element of a given permutation. There is a constant delay per permutation, leading to an O(n!) time solution. This is an improvement over the best previously known techniques in two respects: the algorithm runs on the (arguably) weakest model of parallel computation, and is cost optimal (assuming the time to output the permutations is counted). The algorithm is extended to run adaptively, i.e., when the number of available processors is other than n.     

Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects

In this paper, we study the problem of minimizing the weighted sum of makespan and total completion time in a permutation flowshop where the processing times are supposed to vary according to learning effects. The processing time of a job is a function of the sum of the logarithms of the processing times of the jobs already processed and its position in the sequence. We present heuristic algorithms, which are modified from the optimal schedules for the corresponding single machine scheduling problem and analyze their worst-case error bound. We also adopt an existing algorithm as well as a branch-and-bound algorithm for the general m-machine permutation flowshop problem. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems.