求解总拖期时间最小化流水车间调度问题的多智能体进化算法

针对总拖期时间最小化的置换流水车间调度问题（Total tardiness permutation flow-shop scheduling problem） 提出了一种基于多智能体的进化搜索算法. 在该算法中,采用基于延迟时间排序的学习搜索策略（Tardiness rank based learning）,快速产生高质量的新个体,并根据概率更新模型进行智能体网格的更新进化. 同时通过实验设计的方法探讨了算法参数设置对算法性能的影响. 为了验证算法的性能,求解了Vallada标准测试集中540个测试问题,并将测试结果与一些代表算法进行比较,验证了该算法的有效性.     

Minimizing conditional-value-at-risk for stochastic scheduling problems

This paper introduces the use of conditional-value-at-risk (CVaR) as a criterion for stochastic scheduling problems. This criterion has the tendency of simultaneously reducing both the expectation and variance of a performance measure, while retaining linearity whenever the expectation can be represented by a linear expression. In this regard, it offers an added advantage over traditional nonlinear expectation-variance-based approaches. We begin by formulating a scenario-based mixed-integer program formulation for minimizing CVaR for general scheduling problems. We then demonstrate its application for the single machine total weighted tardiness problem, for which we present both a specialized l-shaped algorithm and a dynamic programming-based heuristic procedure. Our numerical experimental results reveal the benefits and effectiveness of using the CVaR criterion. Likewise, we also exhibit the use and effectiveness of minimizing CVaR in the context of the parallel machine total weighted tardiness problem. We believe that minimizing CVaR is an effective approach and holds great promise for achieving risk-averse solutions for stochastic scheduling problems that arise in diverse practical applications.     

A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem

In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck-tabu search (SB-TS) algorithm by replacing the re-optimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed tabu search optimizes the total weighted tardiness for partial schedules in which some machines are currently assumed to have infinite capacity. In the context of tabu search, the shifting bottleneck heuristic features a long-term memory which helps to diversify the local search. We exploit this synergy to develop a state-of-the-art algorithm for the job shop total weighted tardiness problem (JS-TWT). The computational effectiveness of the algorithm is demonstrated on standard benchmark instances from the literature.     

Local and global dominance conditions for the weighted earliness scheduling problem with no idle time

In this paper, we present dominance conditions for the single machine weighted earliness scheduling problem with no idle time. We also propose an algorithm that can be used to improve upper bounds for the weighted earliness criterion and lower bounds for an earliness/tardiness problem. The computational tests show that the algorithm is superior to an initial heuristic schedule and an existing adjacency condition.     

Local and global dominance conditions for the weighted earliness scheduling problem with no idle time

In this paper, we present dominance conditions for the single machine weighted earliness scheduling problem with no idle time. We also propose an algorithm that can be used to improve upper bounds for the weighted earliness criterion and lower bounds for an earliness/tardiness problem. The computational tests show that the algorithm is superior to an initial heuristic schedule and an existing adjacency condition.     

An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups

In many real-world production systems, it requires an explicit consideration of sequence-dependent setup times when scheduling jobs. As for the scheduling criterion, the weighted tardiness is always regarded as one of the most important criteria in practical systems. While the importance of the weighted tardiness problem with sequence-dependent setup times has been recognized, the problem has received little attention in the scheduling literature. In this paper, we present an ant colony optimization (ACO) algorithm for such a problem in a single-machine environment. The proposed ACO algorithm has several features, including introducing a new parameter for the initial pheromone trail and adjusting the timing of applying local search, among others. The proposed algorithm is experimented on the benchmark problem instances and shows its advantage over existing algorithms. As a further investigation, the algorithm is applied to the unweighted version of the problem. Experimental results show that it is very competitive with the existing best-performing algorithms.     

Multi-objective genetic algorithm and its applications to flowshop scheduling

In this paper, we propose a multi-objective genetic algorithm and apply it to flowshop scheduling. The characteristic features of our algorithm are its selection procedure and elite preserve strategy. The selection procedure in our multi-objective genetic algorithm selects individuals for a crossover operation based on a weighted sum of multiple objective functions with variable weights. The elite preserve strategy in our algorithm uses multiple elite solutions instead of a single elite solution. That is, a certain number of individuals are selected from a tentative set of Pareto optimal solutions and inherited to the next generation as elite individuals. In order to show that our approach can handle multi-objective optimization problems with concave Pareto fronts, we apply the proposed genetic algorithm to a two-objective function optimization problem with a concave Pareto front. Last, the performance of our multi-objective genetic algorithm is examined by applying it to the flowshop scheduling problem with two objectives: to minimize the makespan and to minimize the total tardiness. We also apply our algorithm to the flowshop scheduling problem with three objectives: to minimize the makespan, to minimize the total tardiness, and to minimize the total flowtime.     

Multi-objective colonial competitive algorithm for hybrid flowshop problem

This study analyses the multi-objective optimization in hybrid flowshop problem, in which two conflicting objectives, makespan and total weighted tardiness, are considered to be minimized simultaneously. The multi-objective version of Colonial Competitive Algorithm (CCA) for real world optimization problem is introduced and investigated. In contrast to multi-objective problems solved by CCA, presented in the literature, which used the combination of the objectives as single objective, the proposed algorithm is established on Pareto solutions concepts. Another novelty of this paper is estimating the power of each imperialist by a probabilistic criterion for this multi objective algorithm. Besides that, the variable neighborhood search is implemented as an assimilation strategy. Performance of the algorithm is finally compared with a famous algorithm for scheduling problem, NSGA-II, and the multi-objective form of CCA [28].     

A note on a single machine scheduling problem with generalized total tardiness objective function

In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. A pseudo-polynomial time solution algorithm is proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number of tardy jobs on a single machine. The latter algorithm improves the complexity of an existing pseudo-polynomial algorithm by Lawler. Computational results are presented for both special cases considered.     

基于联姻遗传算法的混合FloWshop提前/拖期调度问题

混合流水车间(Flowshop)提前／拖期调度问题的目标是4~_r-件的提前／拖期惩罚成本最小，这是一个NP完全问题，很难用一般的方法解决。文中首先给出了问题的数学模型，然后采用联姻遗传算法求解该问题。仿真结果表明此算法能有效地解决该类复杂调度问题。     

An effective heuristic method for generalized job shop scheduling with due dates

This paper is concerned with the generalized job shop scheduling problem with due dates wherein the objective is to minimize total job tardiness. An efficient heuristic algorithm called the revised exchange heuristic algorithm (REHA) is presented for solving this problem. It has been shown that the algorithm can be completed in polynomial time. Results, generated over a range of shop sizes with different due date tightness levels, indicate that the proposed technique is capable of yielding notable reductions in total tardiness (over initial schedules) for practical size problems. This suggests that this approach is an efficient scheduling option for this class of complex optimization problems.     

A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop

In this paper we address a hybrid flow shop scheduling problem considering the minimization of the sum of the total earliness and tardiness penalties. This problem is proven to be NP-hard, and consequently the development of heuristic and meta-heuristic approaches to solve it is well justified. So, we propose an ant colony optimization method to deal with this problem. Our proposed method has several features, including some heuristics that specifically take into account both earliness and tardiness penalties to compute the heuristic information values. The performance of our algorithm is tested by numerical experiments on a large number of randomly generated problems. A comparison with solutions performance obtained by some constructive heuristics is presented. The results show that the proposed approach performs well for this problem.     

Two new meta-heuristics for a bi-objective supply chain scheduling problem in flow-shop environment

In this study, an integrated multi-objective production-distribution flow-shop scheduling problem will be taken into consideration with respect to two objective functions. The first objective function aims to minimize total weighted tardiness and make-span and the second objective function aims to minimize the summation of total weighted earliness, total weighted number of tardy jobs, inventory costs and total delivery costs. Firstly, a mathematical model is proposed for this problem. After that, two new meta-heuristic algorithms are developed in order to solve the problem. The first algorithm (HCMOPSO), is a multi-objective particle swarm optimization combined with a heuristic mutation operator, Gaussian membership function and a chaotic sequence and the second algorithm (HBNSGA-II), is a non-dominated sorting genetic algorithm II with a heuristic criterion for generation of initial population and a heuristic crossover operator. The proposed HCMOPSO and HBNSGA-II are tested and compared with a Non-dominated Sorting Genetic Algorithm II (NSGA-II), a Multi-Objective Particle Swarm Optimization (MOPSO) and two state-of-the-art algorithms from recent researches, by means of several comparing criteria. The computational experiments demonstrate the outperformance of the proposed HCMOPSO and HBNSGA-II.     

A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine

This paper deals with the single machine scheduling problem to minimize the total weighted tardiness in the presence of sequence dependent setup. Firstly, a mathematical model is given to describe the problem formally. Since the problem is NP-hard, a general variable neighborhood search (GVNS) heuristic is proposed to solve it. Initial solution for the GVNS algorithm is obtained by using a constructive heuristic that is widely used in the literature for the problem. The proposed algorithm is tested on 120 benchmark instances. The results show that 37 out of 120 best known solutions in the literature are improved while 64 instances are solved equally. Next, the GVNS algorithm is applied to single machine scheduling problem with sequence dependent setup times to minimize the total tardiness problem without changing any implementation issues and the parameters of the GVNS algorithm. For this problem, 64 test instances are solved varying from small to large sizes. Among these 64 instances, 35 instances are solved to the optimality, 16 instances' best-known results are improved, and 6 instances are solved equally compared to the best-known results. Hence, it can be concluded that the GVNS algorithm is an effective, efficient and a robust algorithm for minimizing tardiness on a single machine in the presence of setup times.     

A local-best harmony search algorithm with dynamic sub-harmony memories for lot-streaming flow shop scheduling problem

In this paper, a local-best harmony search (HS) algorithm with dynamic sub-harmony memories (HM), namely DLHS algorithm, is proposed to minimize the total weighted earliness and tardiness penalties for a lot-streaming flow shop scheduling problem with equal-size sub-lots. First of all, to make the HS algorithm suitable for solving the problem considered, a rank-of-value (ROV) rule is applied to convert the continuous harmony vectors to discrete job sequences, and a net benefit of movement (NBM) heuristic is utilized to yield the optimal sub-lot allocations for the obtained job sequences. Secondly, an efficient initialization scheme based on the NEH variants is presented to construct an initial HM with certain quality and diversity. Thirdly, during the evolution process, the HM is dynamically divided into many small-sized sub-HMs which evolve independently so as to balance the fast convergence and large diversity. Fourthly, a new improvisation scheme is developed to well inherit good structures from the local-best harmony vector in the sub-HM. Meanwhile, a chaotic sequence to produce decision variables for harmony vectors and a mutation scheme are utilized to enhance the diversity of the HM. In addition, a simple but effective local search approach is presented and embedded in the DLHS algorithm to enhance the local searching ability. Computational experiments and comparisons show that the proposed DLHS algorithm generates better or competitive results than the existing hybrid genetic algorithm (HGA) and hybrid discrete particle swarm optimization (HDPSO) for the lot-streaming flow shop scheduling problem with total weighted earliness and tardiness criterion.     

Scheduling rules to minimize total tardiness in a parallel machine problem with setup and calendar constraints

Quality control lead times are one of most significant causes of loss of time in the pharmaceutical and cosmetics industries. This is partly due to the organization of laboratories that feature parallel multipurpose machines for chromatographic analyses. The testing process requires long setup times and operators are needed to launch the process. The various controls are non-preemptive and are characterized by a release date, a due date and available routings. These quality processes lead to significant delays, and we therefore evaluate the total tardiness criterion. Previous heuristics were defined for the total tardiness criterion, parallel machines, and setup such as apparent tardiness cost (ATC) and ATC with setups (ATCS). We propose new rules and a simulated annealing procedure in order to minimize total tardiness.     

Interval-indexed formulation based heuristics for single machine total weighted tardiness problem

In this paper, we solve the single machine total weighted tardiness problem by using integer programming and linear programming based heuristic algorithms. Interval-indexed formulation is used to formulate the problem. We discuss several methods to form the intervals and different post-processing methods. Then, we show how our algorithm can be used to improve a population of a genetic algorithm. We also provide some computational results that show the effectiveness of our algorithm. Many aspects of our heuristic algorithm are quite general and can be applied to other scheduling and combinatorial optimization problems.     

Local search heuristics for two-stage flow shop problems with secondary criterion

This paper develops and compares different local search heuristics for the two-stage flow shop problem with makespan minimization as the primary criterion and the minimization of either the total flow time, total weighted flow time, or total weighted tardiness as the secondary criterion. We investigate several variants of simulated annealing, threshold accepting, tabu search, and multi-level search algorithms. The influence of the parameters of these heuristics and the starting solution are empirically analyzed. The proposed heuristic algorithms are empirically evaluated and found to be relatively more effective in finding better quality solutions than the existing algorithms.Scope and purposeTraditional research to solve multi-stage scheduling problems has focused on single criterion. However, in industrial scheduling practices, managers develop schedules based on multi-criteria. Scheduling problems involving multiple criteria require significantly more effort in finding acceptable solutions and hence have not received much attention in the literature. This paper considers one such multiple criteria scheduling problem, namely, the two-machine flow shop problem where the primary criterion is the minimization of makespan and the secondary criterion is one of the three most popular performance measures, namely, the total flow time, total weighted flow time, or total weighted tardiness. Based on the principles of local search, development of heuristic algorithms, that can be adapted for several multi-criteria scheduling problems, is discussed. Using the example of the two-machine flow shop problem with secondary criterion, computational experiments are used to evaluate the utility of the proposed algorithms for solving scheduling problems with a secondary criterion.     

An optimal procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem

We present an optimal solution procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem. In this problem, we assume the constrained renewable resources are limited to very expensive equipments and machines that are used in other projects and are not available in all periods of time of a project. In other words, for each resource, there is a dictated ready date as well as a due date such that no resource can be available before its ready date but the resources are permitted to be used after their due dates by paying penalty cost depending on the resource type. We also assume that only one unit of each resource type is available and no activity needs more than it for execution. The objective is to determine a schedule with minimal total weighted resource tardiness penalty costs. For this purpose, we present a branch-and-bound algorithm in which the branching scheme starts from a graph representing a set of conjunctions (the classical finish-start precedence constraints) and disjunctions (introduced by the resource constraints). In the search tree, each node is branched to two child nodes based on the two opposite directions of each undirected arc of disjunctions. Selection sequence of undirected arcs in the search tree affects the performance of the algorithm. Hence, we developed different rules for this issue and compare the performance of the algorithm under these rules using a randomly generated benchmark problem set.