求解带组换装时间单机调度问题的禁忌搜索算法

以包头某钢铁线材企业生产实际调度问题为背景,研究了一类带组换装时间的单机调度问题.由于该问题是NP难的,本文提出了一类适合该问题的禁忌搜索算法.此外,本文将问题性质引入了禁忌搜索算法以进一步提高算法寻优性能,降低算法运行时间.本文提出的算法在随机问题和实际问题上均进行了测试,实验结果表明,本文提出的算法能在不到10秒的时间内获得实际问题的一个近似最优解.     

A scatter search algorithm for the distributed permutation flowshop scheduling problem

The distributed permutation flowshop problem has been recently proposed as a generalization of the regular flowshop setting where more than one factory is available to process jobs. Distributed manufacturing is a common situation for large enterprises that compete in a globalized market. The problem has two dimensions: assigning jobs to factories and scheduling the jobs assigned to each factory. Despite being recently introduced, this interesting scheduling problem has attracted attention and several heuristic and metaheuristic methods have been proposed in the literature. In this paper we present a scatter search (SS) method for this problem to optimize makespan. SS has seldom been explored for flowshop settings. In the proposed algorithm we employ some advanced techniques like a reference set made up of complete and partial solutions along with other features like restarts and local search. A comprehensive computational campaign including 10 existing algorithms, together with statistical analyses, shows that the proposed scatter search algorithm produces better results than existing algorithms by a significant margin. Moreover all 720 known best solutions for this problem are improved.     

Serial-batching group scheduling with release times and the combined effects of deterioration and truncated job-dependent learning

This paper investigates a single machine serial-batching scheduling problem considering release times, setup time, and group scheduling, with the combined effects of deterioration and truncated job-dependent learning. The objective of the studied problem is to minimize the makespan. Firstly, we analyze the special case where all groups have the same arrival time, and propose the optimal structural properties on jobs sequencing, jobs batching, batches sequencing, and groups sequencing. Next, the corresponding batching rule and algorithm are developed. Based on these properties and the scheduling algorithm, we develop a hybrid VNS–ASHLO algorithm incorporating variable neighborhood search (VNS) and adaptive simplified human learning optimization (ASHLO) algorithms to solve the general case of the studied problem. Computational experiments on randomly generated instances are conducted to compare the proposed VNS–ASHLO with the algorithms of VNS, ASHLO, Simulated Annealing (SA), and Particle Swarm Optimization (PSO). The results based on instances of different scales show the effectiveness and efficiency of the proposed algorithm.     

A tabu search heuristic for ship routing and scheduling with flexible cargo quantities

This paper presents a planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies typically have a certain amount of contract cargoes that they are committed to carry, while trying to maximize their profit from optional spot cargoes. The cargo quantities are often flexible within an interval. Therefore, interwoven with the routing and scheduling decisions, the planner also has to decide the optimal cargo quantities. A tabu search algorithm embedding a specialized heuristic for deciding the optimal cargo quantities in each route is proposed to solve the problem. Computational results show that the heuristic gives optimal or near-optimal solutions to real-life cases of the problem within reasonable time. It is also shown that utilizing the flexibility in cargo quantities gives significantly improved solutions.     

Sequencing and scheduling for filling lines in dairy production

We consider an integrated sequencing and scheduling problem arising at filling lines in dairy industry. Even when a processing sequence is decided, still a scheduling problem has to be solved for the sequence. This incorporates typical side constraints as they occur also in other sequencing problems in practice. Previously, we proposed a framework for general sequencing and scheduling problems: A genetic algorithm is utilized for the sequencing, incorporating a problem specific algorithm for the fixed-sequence scheduling. In this paper, we investigate how this approach performs for filling lines. Based on insights into structural properties of the problem, we propose different scheduling algorithms. In cooperation with Sachsenmilch GmbH, the algorithm was implemented for their bottleneck filling line, and evaluated in an extensive computational study. For the real data from production, our algorithm computes almost optimal solutions. However, as a surprising result, our simple greedy algorithms outperform the more elaborate ones in many aspects, showing interesting directions for future research.     

A tabu search algorithm for solving economic lot scheduling problem

The economic lot scheduling problem has driven considerable amount of research. The problem is NP-hard and recent research is focused on finding heuristic solutions rather than searching for optimal solutions. This paper introduces a heuristic method using a tabu search algorithm to solve the economic lot scheduling problem. Diversification and intensification schemes are employed to improve the efficiency of the proposed Tabu search algorithm. Experimental design is conducted to determine the best operating parameters for the Tabu search. Results show that the tabu search algorithm proposed in this paper outperforms two well known benchmark algorithms.     

A hybrid scatter search heuristic for personalized crew rostering in the airline industry

The crew scheduling problem in the airline industry is extensively investigated in the operations research literature since efficient crew employment can drastically reduce operational costs of airline companies. Given the flight schedule of an airline company, crew scheduling is the process of assigning all necessary crew members in such a way that the airline is able to operate all its flights and constructing a roster line for each employee minimizing the corresponding overall cost for personnel. In this paper, we present a scatter search algorithm for the airline crew rostering problem. The objective is to assign a personalized roster to each crew member minimizing the overall operational costs while ensuring the social quality of the schedule. We combine different complementary meta-heuristic crew scheduling combination and improvement principles. Detailed computational experiments in a real-life problem environment are presented investigating all characteristics of the procedure. Moreover, we compare the proposed scatter search algorithm with optimal solutions obtained by an exact branch-and-price procedure and a steepest descent variable neighbourhood search.     

求解柔性作业车间调度的动态群智能优化算法

针对柔性作业车间调度问题,提出一种新型两阶段动态混合群智能优化算法.算法初始阶段采用动态邻域的协同粒子群进行粗搜索,第二阶段提出了基于混沌算子的蜂群进行细搜索,既增强了种群多样性,又提高了算法搜索精度,实现了全局搜索与局部搜索能力的有效平衡.针对柔性作业车间调度问题特点,采用独特的编码方式和位置更新策略来避免不合法解的产生.最后将此算法在不同规模的实例上进行了仿真测试,并与最近提出的其他几种具有代表性的算法进行了比较,验证了算法的有效性和优越性.     

New block properties for the permutation flow shop problem with application in tabu search

This paper deals with the classic flow-shop scheduling problem with the make-span criterion. Some new properties of the problem associated with the so-called blocks have been presented and discussed. The properties allow us to skip some non-perspective solutions during the search of the solution space. Applied to local search algorithms, they result in a significant reduction of neighbourhood size and quickly direct the search trajectory to promising regions of the solution space. The implementation of the proposed properties in a tabu search algorithm is also presented. Computational experiments (up to 500 jobs and 20 machines) are given and compared with the results yielded by the best known algorithms.     

带有资源转移时间的RCPSP资源流模型及算法

本文在传统资源受限项目调度问题(resource-constrained project scheduling problem, RCPSP)中引入资源转移时间,为有效获得问题的最优解,采用资源流编码方式表示可行解,建立了带有资源转移时间的RCPSP资源流优化模型,目标为最小化项目工期。根据问题特征设计了改进的资源流重构邻域算子,分别设计了改进的禁忌搜索算法和贪心随机自适应禁忌搜索算法求解模型。数据实验结果表明,相较于现有文献中的方法,所提两种算法均可针对更多的项目实例求得最优解,并且得到最优解的时间更短,求解效率更高。此外,分析了算法在求解具有不同特征的项目实例时的性能,所得结果为项目经理结合项目特征评价算法适用性提供了指导。     

Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process

We consider a scheduling problem in a factory producing printed circuit boards (PCBs). The PCB assembly process in this factory can be regarded as a flowshop which has two special characteristics: jobs have sequence dependent setup times and each job consists of a lot (batch) of identical PCBs. Because of the latter characteristic, it is possible to start a job on a following machine before the job is entirely completed on a previous machine, that is, there is time-lag between machines. In this paper, we propose several heuristics, including taboo search (TS) and simulated annealing (SA) methods, for this generalized flowshop scheduling problem with the objective of minimizing mean tardiness. We compare suggested heuristics after series of tests to find appropriate values for parameters needed for the two search algorithms, TS and SA. Results of computational tests on randomly generated test problems are reported.     

A single-machine scheduling problem with two-agent and deteriorating jobs

Deteriorating jobs scheduling problems have been extensively studied in recent years. However, it is assumed that there is a common goal to minimize for all jobs in most of the research. In many management situations, multiple agents compete on the usage of a common processing resource. In this paper, we considered a single-machine scheduling problem with a linear deterioration assumption where the objective is to minimize the total weighted completion time of jobs from the first agent with the restriction that no tardy job is allowed for the second agent. We proposed a branch-and-bound algorithm and three heuristic algorithms to search for the optimal solution and near-optimal solutions, respectively. A computational experiment was conducted to evaluate the performance of the proposed algorithms.     

具有机器适用限制的分布式置换流水车间问题的模型与算法

考虑具有机器适用限制的多个不同置换流水车间的调度问题. 机器适用限制指的是每个工件只能分配到其可加工工厂集合. 所有置换流水车间拥有的机器数相同但是具有不同的加工能力. 首先, 针对该问题建立了基于位置的混合整数线性规划模型; 进而, 对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法. 其次, 基于NEH方法提出了启发式算法NEHg, 并给出了以NEHg为上界的分支定界算法. 最后, 通过例子说明了NEHg启发式算法和分支定界算法的计算过程, 并进行大量的实验将NEHg与NEH算法结果进行比较, 从而验证了NEHg算法的有效性.     

Hybrid evolutionary optimization of the operation of pipeless plants

Pipeless plants are a new production concept in chemical engineering in which automated guided vehicles (AGVs) transport the substances in mobile vessels between processing stations. In the operation of such plants, decisions have to be made on the scheduling of the production, the assignment of the equipment and the routing of the AGVs that carry the vessels. The large number of interacting degrees of freedom prohibit the use of exact mathematical algorithms to compute optimal schedules. This paper describes the combination of an evolutionary scheduling algorithm with a simulation based schedule builder. The algorithm is tested on a real-life example and on a benchmark problem from the literature and yields considerably shorter makespans than a heuristic solution.     

Partitioned Random Search for Global Optimization with Sampling Cost and Discounting Factor

The method of partitioned random search has been proposed in recent years to obtain an as good as possible solution for the global optimization problem (1). A practical algorithm has been developed and applied to real-life problems. However, the design of this algorithm was based mainly on intuition. The theoretical foundation of the method is an important issue in the development of efficient algorithms for such problems. In this paper, we generalize previous theoretical results and propose a sequential sampling policy for the partitioned random search for global optimization with sampling cost and discounting factor. A proof of the optimality of the proposed sequential sampling policy is given by using the theory of optimal stopping.     

Multiobjective evolutionary algorithms to identify highly autocorrelated areas: the case of spatial distribution in financially compromised farms

In this paper, we address the optimal batch sizing and just-in-time scheduling problem where upper and lower bounds on the size of the batches are imposed. The objective is to find a feasible schedule that minimizes the sum of the weighted earliness and tardiness penalties as well as the setup costs, which involves the cost of creating a new batch. We present some structural properties of the optimal schedules and describe solving algorithms for the single machine problem.     

Bi-criteria group scheduling with sequence-dependent setup time in a flow shop

A bi-criteria group scheduling problem in a flow shop with sequence-dependent setup time is investigated in this paper. Manufacturing cell and flow shop are two popular scenarios in industry. Dynamic job releases and machine availabilities are assumed. The goal is to minimize the weighted sum of total weighted completion time and total weighted tardiness, which are aimed at satisfying the producer and customer goals separately. Normalized weights are assigned to both criteria to describe the trade-off between the two objectives. Two different initial solution finding mechanisms are proposed, and a tabu-search-based two-level search algorithm is deve1loped to find optimal/near-optimal solutions for the problem. A mathematical model is also developed and implemented to evaluate the optimality of the results from search algorithms for small problem instances. To further uncover the difference in performance of initial solutions and algorithms, an experimental design is performed and results are reported.     

Scheduling trucks in local depots for door-to-door delivery services

A scheduling method is suggested for trucks delivering and picking up freight between branch offices and a regional depot in door-to-door delivery services. As the objective functions, different levels of customer service resulting from different timing of deliveries and pickups to/from branch offices are considered as well as the travel cost of trucks. Useful properties of the optimal timing of deliveries and pickups are derived to reduce the size of the search space significantly. Numerical experiments were conducted to evaluate various algorithms to solve the problem.     

The break scheduling problem: complexity results and practical algorithms

Break scheduling problems arise in working areas where breaks are indispensable, e.g., in air traffic control, supervision, or assembly lines. We regard such a problem from the area of supervision personnel. The objective is to find a break assignment for an existing shiftplan such that various constraints reflecting legal demands or ergonomic criteria are satisfied and such that staffing requirement violations are minimised. We prove the NP-completeness of this problem when all possible break patterns for each shift are given explicitly as part of the input. To solve our problem we propose two variations of a memetic algorithm. We define genetic operators, a local search based on three neighbourhoods, and a penalty system that helps to avoid local optima. Parameters influencing the algorithms are experimentally evaluated and assessed with statistical methods. We compare our algorithms, each with the best parameter setting according to the evaluation, with the state-of-the-art algorithm on a set of 30 real-life and randomly generated instances that are publicly available. One of our algorithms returns improved results on 28 out of the 30 benchmark instances. To the best of our knowledge, our improved results for the real-life instances constitute new upper bounds for this problem     

A bi-criteria two-machine flowshop scheduling problem with a learning effect

This paper addresses a bi-criteria two-machine flowshop scheduling problem when the learning effect is present. The objective is to find a sequence that minimizes a weighted sum of the total completion time and the maximum tardiness. In this article, a branch-and-bound method, incorporating several dominance properties and a lower bound, is presented to search for the exact solution for small job-size problems. In addition, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm for large job-size problems. Finally, computational results for this problem are provided to evaluate the performance of the proposed algorithms.