Minimizing the total completion time on a single machine with the learning effect and multiple availability constraints

This paper considers a single machine scheduling problem with the learning effect and multiple availability constraints that minimizes the total completion time. To solve this problem, a new binary integer programming model is presented, and a branch-and-bound algorithm is also developed for solving the given problem optimally. Since the problem is strongly NP-hard, to find the near-optimal solution for large-sized problems within a reasonable time, two meta-heuristics; namely, genetic algorithm and simulated annealing are developed. Finally, the computational results are provided to compare the result of the binary integer programming, branch-and-bound algorithm, genetic algorithm and simulated annealing. Then, the efficiency of the proposed algorithms is discussed.     

The use of dynamic programming in genetic algorithms for permutation problems

To deal with computationally hard problems, approximate algorithms are used to provide reasonably good solutions in practical time. Genetic algorithms are an example of the meta-heuristics which were recently introduced and which have been successfully applied to a variety of problems. We propose to use dynamic programming in the process of obtaining new generation solutions in the genetic algorithm, and call it a genetic DP algorithm. To evaluate the effectiveness of this approach, we choose three representative combinatorial optimization problems, the single machine scheduling problem, the optimal linear arrangement problem and the traveling salesman problem, all of which ask to compute optimum permutations of n objects and are known to be NP-hard. Computational results for randomly generated problem instances exhibit encouraging features of genetic DP algorithms.     

稀疏线性规划研究

稀疏线性规划在金融计算、工业生产、装配调度等领域应用十分广泛.本文首先给出稀疏线性规划问题的一般模型并证明问题是NP困难问题;其次采用交替方向乘子法(ADMM)求解该问题;最后证明了算法在近似问题上的收敛性.数值实验表明,算法在大规模数值算例上的表现优于已有的混合遗传算法;同时通过对金融实例的计算验证了算法及模型在稀疏投资组合问题上的有效性.     

Cyclic scheduling for F.M.S.: Modelling and evolutionary solving approach

This paper concerns the domain of flexible manufacturing systems (FMS) and focuses on the scheduling problems encountered in these systems. We have chosen the cyclic behaviour to study this problem, to reduce its complexity. This cyclic scheduling problem, whose complexity is NP-hard in the general case, aims to minimise the work in process (WIP) to satisfy economic constraints. We first recall and discuss the best known cyclic scheduling heuristics. Then, we present a two-step resolution approach. In the first step, a performance analysis is carried out; it is based on the Petri net modelling of the production process. This analysis resolves some indeterminism due to the system’s flexibility and allows a lower bound of the WIP to be obtained. In the second step, after a formal model of the scheduling problem has been given, we describe a genetic algorithm approach to find a schedule which can reach the optimal production speed while minimizing the WIP. Finally, our genetic approach is validated and compared with known heuristics on a set of test problems.     

混合FlowShop环境下的提前／滞后调度问题的遗传算法

讨论了混合Flow Shop环境下的提前/滞后调度问题,这是一个NP-难题。为此,首先给出了问题的数学模型,然后构造了一个有效的遗传算法。最后给出了实验结果和结论。     

Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop

This paper considers the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. It continues recent work by Bräsel et al. [H. Bräsel, A. Herms, M. Mörig, T. Tautenhahn, T. Tusch, F. Werner, Heuristic constructive algorithms for open shop scheduling to minmize mean flow time, European J. Oper. Res., in press (doi.10.1016/j.ejor.2007.02.057)] on constructive algorithms. For this strongly NP-hard problem, we present two iterative algorithms, namely a simulated annealing and a genetic algorithm. For the simulated annealing algorithm, several neighborhoods are suggested and tested together with the control parameters of the algorithm. For the genetic algorithm, new genetic operators are suggested based on the representation of a solution by the rank matrix describing the job and machine orders. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The algorithms are compared relative to each other, and the quality of the results is also estimated partially by a lower bound for the corresponding preemptive open shop problem. For most of the problems, the genetic algorithm is superior when fixing the same number of 30 000 generated solutions for each algorithm. However, in contrast to makespan minimization problems, where the focus is on problems with an equal number of jobs and machines, it turns out that problems with a larger number of jobs than machines are the hardest problems.     

一类具有资源约束和优先加工顺序约束极小化加权总完工时间调度优化问题研究

本文针对工件间具有链状优先约束和relocation资源约束的极小化加权总完工时间调度优化问题展开研究.针对这一NP难问题,利用relocation约束的性质和贪婪算法的思想,设计了一个多项式近似算法,并证明了当链不可中断,每个链具有相同工件数和工件间具有相同加工时间时,2为该算法的紧界.     

On complexity of optimal recombination for flowshop scheduling problems

Under study is the complexity of optimal recombination for various flowshop scheduling problems with the makespan criterion and the criterion of maximum lateness. The problems are proved to be NP-hard, and a solution algorithm is proposed. In the case of a flowshop problem on permutations, the algorithm is shown to have polynomial complexity for “almost all” pairs of parent solutions as the number of jobs tends to infinity.     

考虑机器调整次数和产品质量的卷烟批量计划和柔性流水车间调度集成问题

针对卷烟企业生产中的批量计划和柔性流水车间调度集成问题,构建了整数规划模型,目标函数由卷烟生产时间、生产线调整次数、卷烟质量、库存成本四部分组成。鉴于该问题的NP-hard性,设计遗传算法进行求解,通过合理设计遗传算子,避免不可行解出现。应用某卷烟企业数据得到优化排产结果,与该企业之前依照经验排产方案进行对比,发现优化排程结果在减少品牌转换次数,提高生产的连续性方面具有明显优势。该算法已作为某卷烟企业排产人员的排产参考,应用于排产决策中,取得了良好的效果,对卷烟企业制定排产计划具有一定的实际指导意义。     

Application of an optimization problem in Max-Plus algebra to scheduling problems

The problem tackled in this paper deals with products of a finite number of triangular matrices in Max-Plus algebra, and more precisely with an optimization problem related to the product order. We propose a polynomial time optimization algorithm for 2×2 matrices products. We show that the problem under consideration generalizes numerous scheduling problems, like single machine problems or two-machine flow shop problems. Then, we show that for 3×3 matrices, the problem is NP-hard and we propose a branch-and-bound algorithm, lower bounds and upper bounds to solve it. We show that an important number of results in the literature can be obtained by solving the presented problem, which is a generalization of single machine problems, two- and three-machine flow shop scheduling problems. The branch-and-bound algorithm is tested in the general case and for a particular case and some computational experiments are presented and discussed.     

Computing the metric dimension of graphs by genetic algorithms

In this paper we consider the NP-hard problem of determining the metric dimension of graphs. We propose a genetic algorithm (GA) that uses the binary encoding and the standard genetic operators adapted to the problem. The feasibility is enforced by repairing the individuals. The overall performance of the GA implementation is improved by a caching technique. Since the metric dimension problem up to now has been considered only theoretically, standard test instances for this problem do not exist. For that reason, we present the results of the computational experience on several sets of test instances for other NP-hard problems: pseudo boolean, crew scheduling and graph coloring. Testing on instances with up to 1534 nodes shows that GA relatively quickly obtains approximate solutions. For smaller instances, GA solutions are compared with CPLEX results. We have also modified our implementation to handle theoretically challenging large-scale classes of hypercubes and Hamming graphs. In this case the presented approach reaches optimal or best known solutions for hypercubes up to 131072 nodes and Hamming graphs up to 4913 nodes.     

The single machine total weighted completion time scheduling problem with the sum-of-processing time based models: Strongly NP-hard

Although the single machine scheduling problem to minimize the total weighted completion times with the sum-of-processing time based learning or aging effects have been known for a decade, it is still an open question whether these problems are strongly NP-hard. We resolve this issue and prove them to be strongly NP-hard with the learning effect as well as with the aging effect. Furthermore, we construct an exact parallel branch and bound algorithm for the problem with general sum-of-processing time based models, which can solve optimally moderate problem instances in reasonable time.     

Minimizing earliness and tardiness penalties in a single-machine problem with a common due date

Scheduling problems involving both earliness and tardiness costs have received significant attention in recent years. This type of problem became important with the advent of the just-in-time (JIT) concept, where early or tardy deliveries are highly discouraged. In this paper we examine the single-machine scheduling problem with a common due date. Performance is measured by the minimization of the sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, we propose a tabu search-based heuristic and a genetic algorithm which exploit specific properties of the optimal solution. Hybrid strategies are also analyzed to improve the performance of these methods. The proposed approaches are examined through a computational comparative study with 280 benchmark problems with up to 1000 jobs.     

Differential evolution for sequencing and scheduling optimization

This paper presents a stochastic method based on the differential evolution (DE) algorithm to address a wide range of sequencing and scheduling optimization problems. DE is a simple yet effective adaptive scheme developed for global optimization over continuous spaces. In spite of its simplicity and effectiveness the application of DE on combinatorial optimization problems with discrete decision variables is still unusual. A novel solution encoding mechanism is introduced for handling discrete variables in the context of DE and its performance is evaluated over a plethora of public benchmarks problems for three well-known NP-hard scheduling problems. Extended comparisons with the well-known random-keys encoding scheme showed a substantially higher performance for the proposed. Furthermore, a simple slight modification in the acceptance rule of the original DE algorithm is introduced resulting to a more robust optimizer over discrete spaces than the original DE.     

A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines

This paper deals with a scheduling problem of independent tasks with common due date where the objective is to minimize the total weighted tardiness. The problem is known to be ordinary NP-hard in the case of a single machine and a dynamic programming algorithm was presented in the seminal work of Lawler and Moore [E.L. Lawler, J.M. Moore, A functional equation and its application to resource allocation and sequencing problems, Management Science 16 (1969) 77–84]. In this paper, this algorithm is described and discussed. Then, a new dynamic programming algorithm is proposed for solving the single machine case. These methods are extended for solving the identical and uniform parallel-machine scheduling problems.     

A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan

It is well known that the flow-shop scheduling problem (FSSP) is a branch of production scheduling and is NP-hard. Now, many different approaches have been applied for permutation flow-shop scheduling to minimize makespan, but current algorithms even for moderate size problems cannot be solved to guarantee optimality. Some literatures searching PSO for continuous optimization problems are reported, but papers searching PSO for discrete scheduling problems are few. In this paper, according to the discrete characteristic of FSSP, a novel particle swarm optimization (NPSO) algorithm is presented and successfully applied to permutation flow-shop scheduling to minimize makespan. Computation experiments of seven representative instances (Taillard) based on practical data were made, and comparing the NPSO with standard GA, we obtain that the NPSO is clearly more efficacious than standard GA for FSSP to minimize makespan.     

A genetic algorithm for multi-mode resource constrained project scheduling problem

This article considers a general class of nonpreemptive multi-mode resource-constrained project scheduling problems in which activity durations depend on committed renewable resources (multi-mode time resource tradeoff). We propose a genetic algorithm for these problems and compare it with a stochastic scheduling method proposed by Drexl and Gruenewald. Computational results show that the proposed genetic algorithm is superior to the stochastic scheduling method.     

On the geometry,preemptions and complexity of multiprocessor and shop scheduling

In this paper we study multiprocessor and open shop scheduling problems from several points of view. We explore a tight dependence of the polynomial solvability/intractability on the number of allowed preemptions. For an exhaustive interrelation, we address the geometry of problems by means of a novel graphical representation. We use the so-called preemption and machine-dependency graphs for preemptive multiprocessor and shop scheduling problems, respectively. In a natural manner, we call a scheduling problem acyclic if the corresponding graph is acyclic. There is a substantial interrelation between the structure of these graphs and the complexity of the problems. Acyclic scheduling problems are quite restrictive; at the same time, many of them still remain NP-hard. We believe that an exhaustive study of acyclic scheduling problems can lead to a better understanding and give a better insight of general scheduling problems. We show that not only acyclic but also a special non-acyclic version of periodic job-shop scheduling can be solved in polynomial (linear) time. In that version, the corresponding machine dependency graph is allowed to have a special type of the so-called parti-colored cycles. We show that trivial extensions of this problem become NP-hard. Then we suggest a linear-time algorithm for the acyclic open-shop problem in which at most m−2 preemptions are allowed, where m is the number of machines. This result is also tight, as we show that if we allow one less preemption, then this strongly restricted version of the classical open-shop scheduling problem becomes NP-hard. In general, we show that very simple acyclic shop scheduling problems are NP-hard. As an example, any flow-shop problem with a single job with three operations and the rest of the jobs with a single non-zero length operation is NP-hard. We suggest linear-time approximation algorithm with the worst-case performance of ( , respectively) for acyclic job-shop (open-shop, respectively), where (‖ℳ‖, respectively) is the maximal job length (machine load, respectively). We show that no algorithm for scheduling acyclic job-shop can guarantee a better worst-case performance than . We consider two special cases of the acyclic job-shop with the so-called short jobs and short operations (restricting the maximal job and operation length) and solve them optimally in linear time. We show that scheduling m identical processors with at most m−2 preemptions is NP-hard, whereas a venerable early linear-time algorithm by McNaughton yields m−1 preemptions. Another multiprocessor scheduling problem we consider is that of scheduling m unrelated processors with an additional restriction that the processing time of any job on any machine is no more than the optimal schedule makespan C _max^*. We show that the (2m−3)-preemptive version of this problem is polynomially solvable, whereas the (2m−4)-preemptive version becomes NP-hard. For general unrelated processors, we guarantee near-optimal (2m−3)-preemptive schedules. The makespan of such a schedule is no more than either the corresponding non-preemptive schedule makespan or max {C _max^*,p _max}, where C _max^* is the optimal (preemptive) schedule makespan and p _max is the maximal job processing time. E.V. Shchepin was partially supported by the program “Algebraical and combinatorial methods of mathematical cybernetics” of the Russian Academy of Sciences. N. Vakhania was partially supported by CONACyT grant No. 48433.     

Single machine bicriteria scheduling with equal-length jobs to minimize total weighted completion time and maximum cost

Bicriteria scheduling problems are of significance in both theoretical and applied aspects. It is known that the single machine bicriteria scheduling problem of minimizing total weighted completion time and maximum cost simultaneously is strongly NP-hard. In this paper we consider a special case where the jobs have equal length and present an $O(n^{3}\log n)$ algorithm for finding all Pareto optimal solutions of this bicriteria scheduling problem.     

Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization

In this paper, a HGA (hybrid genetic algorithm) is proposed for permutation flowshop scheduling problems (PFSP) with total flowtime minimization, which are known to be NP-hard. One of the chromosomes in the initial population is constructed by a suitable heuristic and the others are yielded randomly. An artificial chromosome is generated by a weighted simple mining gene structure, with which a new crossover operator is presented. Additionally, two effective heuristics are adopted as local search to improve all generated chromosomes in each generation. The HGA is compared with one of the most effective heuristics and a recent meta-heuristic on 120 benchmark instances. Experimental results show that the HGA outperforms the other two algorithms for all cases. Furthermore, HGA obtains 115 best solutions for the benchmark instances, 92 of which are newly discovered.