SOLVING THE OPEN SHOP SCHEDULING PROBLEM VIA A HYBRID GENETIC-VARIABLE NEIGHBORHOOD SEARCH ALGORITHM

In this article, a hybrid metaheuristic method for solving the open shop scheduling problem (OSSP) is proposed. The optimization criterion is the minimization of makespan and the solution method consists of four components: a randomized initial population generation, a heuristic solution included in the initial population acquired by a Nawaz-Enscore-Ham (NEH)-based heuristic for the flow shop scheduling problem, and two interconnected metaheuristic algorithms: a variable neighborhood search and a genetic algorithm. To our knowledge, this is the first hybrid application of genetic algorithm (GA) and variable neighborhood search (VNS) for the open shop scheduling problem. Computational experiments on benchmark data sets demonstrate that the proposed hybrid metaheuristic reaches a high quality solution in short computational times. Moreover, 12 new hard, large-scale open shop benchmark instances are proposed that simulate realistic industrial cases.     

A variable neighborhood search approach for planning and scheduling of jobs on unrelated parallel machines

In this paper, we study a planning and scheduling problem for unrelated parallel machines. There are n jobs that have to be assigned and sequenced on m unrelated parallel machines. Each job has a weight that represents the priority of the corresponding customer order, a given due date, and a release date. An Automated Guided Vehicle is used to transport at maximum Load _max jobs into a storage space in front of the machines in a given period of time. We consider t _max consecutive periods. We are interested in minimizing the total weighted tardiness of the jobs across the periods. This measure is important when we are interested in a good on-time delivery performance. We present an appropriate mixed integer program. To solve this NP-hard problem, we develop a heuristic methodology based on decomposition and variable neighborhood search (VNS). The proposed approaches are assessed using randomly generated problem instances. We compare them with a simple heuristic based on decomposition and list scheduling using the Apparent Tardiness Cost dispatching rule. The results demonstrate that the heuristic approach based on VNS performs comparably to the mixed integer program while having reasonable solution times and outperforms the simple heuristic and a genetic algorithm (GA) from previous research.     

Satisfying due-dates in the presence of sequence dependent family setups with a special comedown structure

This paper addresses a static, n-job, single-machine scheduling problem with sequence dependent family setups. The setup matrix follows a special structure where a constant setup is required only if a job from a smaller indexed family is an immediate successor of one from a larger indexed family. The objective is to minimize the maximum lateness (L_max). A two-step neighborhood search procedure and an implicit enumeration scheme are proposed. Both procedures exploit the problem structure. The enumeration scheme produces optimum solutions to small and medium sized problems in reasonable computational times, yet it fails to perform efficiently in larger instances. Computational results show that the heuristic procedure is highly effective, and is efficient even for extremely large problems.     

约束满足混合算法求解提前/拖期Job Shop调度问题

针对提前/拖期Job Shop调度问题,建立其约束满足优化问题模型,提出了一种约束满足与禁忌搜索结合的混合算法。该算法基于约束满足思想,通过约束传播技术和启发式修复算法,得到可行调度作为禁忌搜索算法的初始解;再进行关键路径上的邻域变换,优化当前解;并采用一种全局邻域交换策略,扩大搜索空间,改善优化结果。数据实验表明了该混合算法的可行性和有效性。     

Single machine scheduling to minimize total weighted late work: a comparison of scheduling rules and search algorithms

In this research the problem of scheduling n jobs to minimize the Total Weighted Late Work (TWLW) is evaluated within the single machine context. As the problem complexity increases, so does the solution complexity, and often the objective is to identify a heuristic or algorithm that may return a near optimal solution. Various scheduling rules, heuristics and algorithms, including the weighted shortest processing rule, a variation of the modified due date rule, a genetic algorithm, neighborhood job search, and space smoothing with neighborhood job search, are empirically evaluated using different parameters to determine the utility of each approach.     

New Genetic Algorithms Based Approaches to Continuous <Emphasis Type="Italic">p</Emphasis>-Median Problem

We proposed new genetic algorithms (GAs) to address well-known p-median problem in continuous space. Two GA approaches with different replacement procedures are developed to solve this problem. To make the approaches more efficient in finding near-optimal solution two hybrid algorithms are developed combining the new GAs and a traditional local search heuristic. The performance of the newly developed models is compared to that of the traditional alternating location-allocation heuristics by numerical simulation and it is found that the models are effective in finding optimum facility locations.     

A HYBRID METAHEURISTIC FOR THE SINGLE-MACHINE TOTAL WEIGHTED TARDINESS PROBLEM

This article presents a new hybrid algorithm for combinatorial optimization that combines differential evolution (DE) with variable neighborhood search (VNS). DE (a population heuristic for optimization over continuous search spaces) is used as global optimizer for solution evolution guiding the search toward the optimal regions of the search space; VNS (a random local search heuristic based on the systematic change of neighborhood) is used as a local optimizer performing a sequence of local changes on individual DE solutions until a local optimum is found. The effectiveness of a DE-VNS approach is demonstrated on the solution of the single-machine total weighted tardiness scheduling problem. The concepts of Lamarckian and Baldwinian learning are also investigated and discussed. Experiments on known benchmark data sets show that DE-VNS with Lamarckian learning can produce high-quality schedules in a rather short computation time. DE-VNS uses a self-adapted mechanism for tuning the required control parameters, a critical feature rendering it applicable to real-life scheduling problems.     

A discrete particle swarm optimization algorithm for scheduling parallel machines

As a novel evolutionary technique, particle swarm optimization (PSO) has received increasing attention and wide applications in a variety of fields. To our knowledge this paper investigates the first application of PSO algorithm to tackle the parallel machines scheduling problem. Proposing equations analogous to those of the classical PSO equations, we present a discrete PSO algorithm (DPSO) to minimize makespan (C_max) criterion. We also investigate the effectiveness of DPSO algorithm through hybridizing it with an efficient local search heuristic. To verify the performance of DPSO algorithm and its hybridized version (HDPSO), comparisons are made through using a recently proposed simulated annealing algorithm for the problem, addressed in the literature, as a comparator algorithm. Computational results signify that the proposed DPSO algorithm is very competitive and can be rapidly guided when hybridizing with a local search heuristic.     

Minimizing the makespan on a single machine with flexible maintenances and jobs’ release dates

This paper addresses the production scheduling problem on a single machine with flexible periodic preventive maintenances (PM), where jobs’ release dates are also considered. Both resumable and non-resumable cases are studied. For the resumable case, it is proved that the problem can be solved in polynomial time with Earliest Release Date (ERD) rule. For the non-resumable case, it is proved to be NP-Hard in strong sense. And, a mixed integer programming (MIP) mathematical model is provided. Then, an effective heuristic ERD-LPT based on the properties of optimal solution is proposed. Meanwhile, a branch-and-bound algorithm (B and B) that utilizes several dominance rules is developed to search the optimal schedule for small-to-medium sized problems. Computational results indicate that the proposed heuristic is highly accurate and the two algorithms are complementary in dealing with different sized problems. Furthermore, the improvement of the integration between production scheduling and PM is significant compared with the First-in-First-out (FIFO) rule which is adopted commonly in industry.     

An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem

Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. Although the traditional optimization algorithms could obtain preferable results in solving the mono-objective FJSP. However, they are very difficult to solve multi-objective FJSP very well. In this paper, a particle swarm optimization (PSO) algorithm and a tabu search (TS) algorithm are combined to solve the multi-objective FJSP with several conflicting and incommensurable objectives. PSO which integrates local search and global search scheme possesses high search efficiency. And, TS is a meta-heuristic which is designed for finding a near optimal solution of combinatorial optimization problems. Through reasonably hybridizing the two optimization algorithms, an effective hybrid approach for the multi-objective FJSP has been proposed. The computational results have proved that the proposed hybrid algorithm is an efficient and effective approach to solve the multi-objective FJSP, especially for the problems on a large scale.     

Solving job shop scheduling with setup times through constraint-based iterative sampling: an experimental analysis

This paper presents a heuristic algorithm for solving a job-shop scheduling problem with sequence dependent setup times and min/max separation constraints among the activities (SDST-JSSP/max). The algorithm relies on a core constraint-based search procedure, which generates consistent orderings of activities that require the same resource by incrementally imposing precedence constraints on a temporally feasible solution. Key to the effectiveness of the search procedure is a conflict sampling method biased toward selection of most critical conflicts and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This constraint-based search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically both on a set of previously studied job-shop scheduling benchmark problems with sequence dependent setup times and by introducing a new benchmark with setups and generalized precedence constraints.     

Minimizing makespan subject to minimum flowtime on two identical parallel machines

We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a computational study to compare the performance of the proposed algorithms with a known heuristic shows that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.Scope and purposeMultiple objective optimization problems are quite common in practice. However, while solving scheduling problems, optimization algorithms often consider only a single objective function. Consideration of multiple objectives makes even the simplest multi-machine scheduling problems NP-hard. Therefore, enumerative optimization techniques and heuristic solution procedures are required to solve multi-objective scheduling problems. This paper illustrates the development of an optimization algorithm and polynomially bounded heuristic solution procedures for the scheduling jobs on two identical parallel machines to hierarchically minimize the makespan subject to the optimality of the total flowtime.     

Parallel machine selection and job scheduling to minimize machine cost and job tardiness

This paper discusses the problem of simultaneously selecting and scheduling parallel machines to minimize the sum of machine holding cost and job tardiness cost. A combinatorial optimization model is developed for this purpose. Solving the developed model is NP-hard. A heuristic algorithm is developed to locate the optimal or near optimal solutions based on a Tabu search mechanism specially designed to control the search process in the solution neighborhood for jobs scheduled on specific machines. Numerical examples show that the solutions of the model lead to compromises between the system cost related to machine selection and the operational cost related to job tardiness penalties. The examples also show that the developed algorithm is effective and computationally efficient.     

A hybrid genetic algorithm with multiple decoding methods for energy-aware remanufacturing system scheduling problem

Remanufacturing system scheduling is an essential and effective approach to realize the digitization and greening of the remanufacturing industry. However, previous researches on the remanufacturing system scheduling problem mainly consider a single or two production stages and economic objectives. In this paper, by integrating the three core production stages, i.e., disassembly, reprocessing and reassembly together, we study the energy-aware remanufacturing system scheduling problem in which the well-accepted Turn Off and On strategy is also considered. First, a mathematical model aiming at minimizing the total energy consumption (TEC) of the remanufacturing system is established. Then, a hybrid genetic algorithm based on variable neighborhood search (GAVNS) solution method is proposed, given the NP-hard nature of the problem. In GAVNS, each chromosome is encoded by a job sequence and three different decoding methods are specially designed according to the formation of optimization objective TEC. To enhance the algorithm's local search capability, the variable neighborhood search technique is introduced. The feasibility and effectiveness of GAVNS in addressing the energy-aware remanufacturing system scheduling problem is verified through simulation experiments on a set of designed test instances. Experimental results also demonstrate that: (1) the Turn Off and On strategy can effectively reduce TEC of the remanufacturing system, which can reach an energy saving rate of 6.68%; (2) the performance of those decoding methods varies with respect to the problem size; (3) the decoding method based on minimizing the energy consumption of the remanufacturing system (namely DM3) has the best performance among the three decoding methods in most cases; (4) GAVNS is more effective than its four peers, i.e., a variant GAVNS_R, iterated greedy algorithm (IG), extended artificial bee colony algorithm (EABC), discrete invasive weed optimization algorithm (DIWO) in seeking the optimal schedule.     

A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system

Effective task scheduling, which is essential for achieving high performance in a heterogeneous multiprocessor system, remains a challenging problem despite extensive studies. In this article, a heuristic-based hybrid genetic-variable neighborhood search algorithm is proposed for the minimization of makespan in the heterogeneous multiprocessor scheduling problem. The proposed algorithm distinguishes itself from many existing genetic algorithm (GA) approaches in three aspects. First, it incorporates GA with the variable neighborhood search (VNS) algorithm, a local search metaheuristic, to exploit the intrinsic structure of the solutions for guiding the exploration process of GA. Second, two novel neighborhood structures are proposed, in which problem-specific knowledge concerned with load balancing and communication reduction is utilized respectively, to improve both the search quality and efficiency of VNS. Third, the proposed algorithm restricts the use of GA to evolve the task-processor mapping solutions, while taking advantage of an upward-ranking heuristic mostly used by traditional list scheduling approaches to determine the task sequence assignment in each processor. Empirical results on benchmark task graphs of several well-known parallel applications, which have been validated by the use of non-parametric statistical tests, show that the proposed algorithm significantly outperforms several related algorithms in terms of the schedule quality. Further experiments are carried out to reveal that the proposed algorithm is able to maintain high performance within a wide range of parameter settings.     

Glass container production scheduling through hybrid multi-population based evolutionary algorithm

Driven by a real-world application in the capital-intensive glass container industry, this paper provides the design of a new hybrid evolutionary algorithm to tackle the short-term production planning and scheduling problem. The challenge consists of sizing and scheduling the lots in the most cost-effective manner on a set of parallel molding machines that are fed by a furnace that melts the glass. The solution procedure combines a multi-population hierarchically structured genetic algorithm (GA) with a simulated annealing (SA), and a tailor-made heuristic named cavity heuristic (CH). The SA is applied to intensify the search for solutions in the neighborhood of the best individuals found by the GA, while the CH determines quickly values for a relevant decision variable of the problem: the processing speed of each machine. The results indicate the superior performance of the proposed approach against a state-of-the-art commercial solver, and compared to a non-hybridized multi-population GA.     

Parts loading scheduling in a flexible forging machine using an advanced genetic algorithm

A flexible forging machine (FFM) is one of the most important machines in a general flexible manufacturing system. The scheduling problem of parts loading in FFM is to reduce or preferably eliminate the changeover cost, and is an NP (Nondeterministic Polynomial solvable)-hard combinatorial optimization problem. The genetic algorithm (GA) is known to be a modern heuristic search algorithm, and is suitable for solving such a problem. When applying GA to the scheduling problem, we frequently obtain a local optimal solution rather than a best approximate solution. The goal of this paper is to solve the above-mentioned problem of falling into a local optimal solution by introducing a measure of diversity of population using the concept of information entropy. Thus, we can obtain a best approximate solution of the parts loading scheduling problem of FFM by using an advanced GA.     

Network-based hybrid genetic algorithm for scheduling in FMS environments

Scheduling in flexible manufacturing systems (FMS) must take account of the shorter lead-time, the multiprocessing environment, the flexibility of alternative workstations with different processing times, and the dynamically changing states. The best scheduling approach, as described here, is to minimize makespan t _M, total flow time t _F, and total tardiness penalty p _T. However, in the case of manufacturing system problems, it is difficult for those with traditional optimization techniques to cope with this. This article presents a new flow network-based hybrid genetic algorithm (hGA) approach for generating static schedules in a FMS environment. The proposed method is combined with the neighborhood search technique in a mutation operation to improve the solution of the FMS problem, and to enhance the performance of the genetic search process. We update the change in swap mutation and the local search-based mutation ration. Numerical experiments show that the proposed flow network-based hGA is both effective and efficient for FMS problems.This work was presented in part at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24–26, 2003     

针对移动云计算任务迁移的快速高效调度算法

计算量较大的应用程序由于需要大量的能耗,因此在电池容量有限的移动设备上运行时十分受限。云计算迁移技术是保证此类应用程序在资源有限的设备上运行的主流方法。针对无线网络中应用程序任务图的调度和迁移问题,提出了一种快速高效的启发式算法。该算法将能够迁移到云端的任务都安排在云端完成这种策略作为初始解,通过逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端,并依据任务间的通讯时间及时更新各个任务的能耗节省量。为了寻找全局最优解,构造了适用于此问题的禁忌搜索算法,给出了相应的编码方法、禁忌表、邻域解以及算法终止准则。构造的禁忌搜索算法以提出的启发式解为初始解进行全局搜索,并实现对启发解的进一步优化。通过 实验 将所提方法与无迁移、随机迁移、饱和迁移3类算法进行对比,结果表明提出的启发式算法能够快速有效地给出能耗更小的解。例如,在宽度为10的任务图上,当深度为8时,无迁移、随机迁移与饱和迁移的能耗分别为5461、3357和2271能量单位,而给出的启发解对应的能耗仅为2111。在此基础上禁忌搜索算法又将其能耗降低到1942, 这进一步说明了提出的启发式算法能够产生高质量的近似解。     

Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems

In our previous researches, we proposed the artificial chromosomes with genetic algorithm (ACGA) which combines the concept of the Estimation of Distribution Algorithms (EDAs) with genetic algorithms (GAs). The probabilistic model used in the ACGA is the univariate probabilistic model. We showed that ACGA is effective in solving the scheduling problems. In this paper, a new probabilistic model is proposed to capture the variable linkages together with the univariate probabilistic model where most EDAs could use only one statistic information. This proposed algorithm is named extended artificial chromosomes with genetic algorithm (eACGA). We investigate the usefulness of the probabilistic models and to compare eACGA with several famous permutation-oriented EDAs on the benchmark instances of the permutation flowshop scheduling problems (PFSPs). eACGA yields better solution quality for makespan criterion when we use the average error ratio metric as their performance measures. In addition, eACGA is further integrated with well-known heuristic algorithms, such as NEH and variable neighborhood search (VNS) and it is denoted as eACGA_hybrid to solve the considered problems. No matter the solution quality and the computation efficiency, the experimental results indicate that eACGA_hybrid outperforms other known algorithms in literature. As a result, the proposed algorithms are very competitive in solving the PFSPs.