Ant colony optimization algorithm for scheduling jobs with fuzzy processing time on parallel batch machines with different capacities

We study the problem of scheduling on parallel batch processing machines with different capacities under a fuzzy environment to minimize the makespan. The jobs have non-identical sizes and fuzzy processing times. After constructing a mathematical model of the problem, we propose a fuzzy ant colony optimization (FACO) algorithm. Based on the machine capacity constraint, two candidate job lists are adopted to select the jobs for building the batches. Moreover, based on the unoccupied space of the solution, heuristic information is designed for each candidate list to guide the ants. In addition, a fuzzy local optimization algorithm is incorporated to improve the solution quality. Finally, the proposed algorithm is compared with several state-of-the-art algorithms through extensive simulated experiments and statistical tests. The comparative results indicate that the proposed algorithm can find better solutions within reasonable time than all the other compared algorithms.     

不同容量平行机下差异工件尺寸的批调度算法

在容量不同的平行批处理机环境下, 针对工件带有不同尺寸和机器适用限制的最小化制造跨度的批调度问题, 提出一种有效的蚁群优化算法. 该算法基于解的浪费空间定义启发式信息, 针对机器容量约束提出两种用于构建解的候选集, 从而有效缩小搜索空间, 并引入局部优化方法提高解的质量. 仿真实验结果表明, 所提出算法具有较好的性能, 并且优于已有的其他算法.

     

An ACO algorithm for makespan minimization in parallel batch machines with non-identical job sizes and incompatible job families

We study the problem of scheduling a set of N jobs with non-identical job sizes from F different families on a set of M parallel batch machines; the objective is to minimize the makespan. The problem is known to be NP-hard. A meta-heuristic based on Max–Min Ant System (MMAS) is presented. The performance of the algorithm is compared with several previously studied algorithms by computational experiments. According to our results, the average distance between the solutions found by our proposed algorithm and the lower bounds is about 4% less than that of the best of all the compared algorithms, demonstrating that our algorithm outperforms the previously studied algorithms.     

A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes

This paper investigates the scheduling problem of parallel identical batch processing machines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and processing time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Based on developing heuristic approaches, we proposed a hybrid genetic heuristic (HGH) to minimize makespan objective. To verify the performance of our algorithm, comparisons are made through using a simulated annealing (SA) approach addressed in the literature as a comparator algorithm. Computational experiments reveal that affording the knowledge of problem through using heuristic procedures, gives HGH the ability of finding optimal or near optimal solutions in a reasonable time.     

Scheduling unrelated parallel batch processing machines with non-identical job sizes

Scheduling unrelated parallel batch processing machines to minimize makespan is studied in this paper. Jobs with non-identical sizes are scheduled on batch processing machines that can process several jobs as a batch as long as the machine capacity is not violated. Several heuristics based on best fit longest processing time (BFLPT) in two groups are proposed to solve the problem. A lower bound is also proved to evaluate the quality of the heuristics. Computational experiments were undertaken. These showed that J_SC-BFLPT, considering both load balance of machines and job processing times, was robust and outperformed other heuristics for most of the problem categories.     

差异工件流水车间批调度问题的求解

针对流水车间批调度问题,提出一种基于群智能算法的求解思路。结合问题具体特点,给出工件集合的分批策略,设计了将Palmer和Best Fit（BF）分批规则相结合的分批方法;在批排序阶段,提出了一种改进的微粒群算法;在粒子初始生成阶段,通过引入NEH启发式算法改进了粒子的初始化质量;在全局最佳位置更新前,通过变邻域搜索优化了算法的局部搜索能力,避免了算法陷入局部最优。仿真实验表明,改进后的算法优于传统的微粒群算法和NEH启发式算法。     

Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times

This research analyzes the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization of the identical parallel processing machines and is closer to real-world production systems. Each machine can accommodate and process several jobs simultaneously as a batch as long as the machine capacity is not exceeded. The batch processing time and the batch ready time are respectively equal to the largest processing time and the largest ready time among all the jobs in the batch. Motivated by the computational complexity and the practical relevance of the problem, we present several heuristics based on first-fit and best-fit earliest job ready time rules. We also present a mixed integer programming model for the problem and a lower bound to evaluate the quality of the heuristics. The small computational effort of deterministic heuristics, which is valuable in some practical applications, is also one of the reasons that motivates this study. The results show that the heuristic proposed in this paper has a superior performance compared to the heuristics based on ideas proposed in the literature.     

差异容量平行批机器环境下基于弱选择约束的调度算法

研究动态到达的差异工件在容量不同的平行批处理机环境下,最小化制造跨度的调度问题,并提出一种有效的元启发式算法.给出一个下界以评价算法的性能,针对所构建批的第1个工件的选择提出弱约束标准及两个基于弱约束的首工件选择策略,并引入到蚁群优化算法.最后通过仿真实验将所提出的改进蚁群算法与已有算法和使用传统选择策略的蚁群算法进行比较,实验结果表明,在建批过程中使用首工件弱约束策略和弱约束下工件尺寸大高概率选择策略是有效的,所提算法的搜索性能较其他算法具有明显优势.     

基于自由搜索算法求解单机差异工件批调度问题*

采用自由搜索（free search,FS）算法对单机差异工件批调度问题的制作跨度进行优化。针对该问题的离散优化特征以及自由搜索算法的不足,将自由搜索算法与实数编码遗传算法相结合,在标准FS算法的基础上引入两种杂交算子和精英保留策略,提出混合自由搜索（hybrid free search,HFS）算法。仿真实验结果表明,该算法表现出良好的鲁棒性和收敛性,与标准FS、FFLPT以及BFLPT算法相比,HFS算法提高了寻优精度。     

Online batch scheduling on parallel machines with delivery times

We study the online batch scheduling problem on parallel machines with delivery times. Online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m=2 or m=3, respectively. When m≥4, we present an online algorithm with a competitive ratio of 1.5+o(1).     

求解差异工件批调度问题的改进型蚁群算法

针对最小化制造跨度的差异工件尺寸单批处理机调度问题,通过将其转化为最小化浪费空间的问题,采用候选集策略构建分批以减少搜索空间,利用基于浪费空间的启发式更新信息素,提出一种改进的最大最小蚁群算法。此外,在算法中还引入了一种局部优化策略,以进一步提高算法的性能。仿真实验结果表明,所提出的算法优于其他几种已有算法,验证了所提出算法的有效性和鲁棒性。     

Constrained binary artificial bee colony to minimize the makespan for single machine batch processing with non-identical job sizes

This paper proposes an artificial bee colony approach to minimize the makespan for a single batch-processing machine. The single batch-processing problem is characterized by discontinuity in the objective function and having integer variables. Since the problem under study is NP-hard, an artificial bee colony approach is proposed. The penalty function method is used to convert the constrained problem to unconstrained problem, which is then solved by the ABC algorithm. A procedure to generate initial solutions is presented, which is based on filling partially filled batches first. The analysis in the article shows that the colony size, the value of the penalty parameter, the penalty function iteration, the ABC iteration, and maximum trials per food source all have a significant effect on the performance of the ABC algorithm; however, no pattern can be established.     

A genetic algorithm application using fuzzy processing times in non-identical parallel machine scheduling problem

There are many scheduling problems which are NP-hard in the literature. Several heuristics and dispatching rules are proposed to solve such hard combinatorial optimization problems. Genetic algorithms (GA) have shown great advantages in solving the combinatorial optimization problems in view of its characteristic that has high efficiency and that is fit for practical application [1]. Two different scale numerical examples demonstrate the genetic algorithm proposed is efficient and fit for larger scale identical parallel machine scheduling problem for minimizing the makespan. But, even though it is a common problem in the industry, only a small number of studies deal with non-identical parallel machines. In this article, a kind of genetic algorithm based on machine code for minimizing the processing times in non-identical machine scheduling problem is presented. Also triangular fuzzy processing times are used in order to adapt the GA to non-identical parallel machine scheduling problem in the paper. Fuzzy systems are excellent tools for representing heuristic, commonsense rules. That is why we try to use fuzzy systems in this study.     

An ant colony-based algorithm for integrated scheduling on batch machines with non-identical capacities

In this paper, a production–distribution scheduling problem with non-identical batch machines and multiple vehicles is considered. In the production stage, n jobs are grouped into batches, which are processed on m parallel non-identical batch machines. In the distribution stage, there are multiple vehicles with identical capacities to deliver jobs to customers after the jobs are processed. The objective is to minimize the total weighted tardiness of the jobs. Considering the NP-hardness of the studied problem, an algorithm based on ant colony optimization is presented. A new local optimization strategy called LOC is proposed to improve the local exploitation ability of the algorithm and further search the neighborhood solution to improve the quality of the solution. Moreover, two interval candidate lists are proposed to reduce the search for the feasible solution space and improve the search speed. Furthermore, three objective-oriented heuristics are developed to accelerate the convergence of the algorithm. To verify the performance of the proposed algorithm, extensive experiments are carried out. The experimental results demonstrate that the proposed algorithm can provide better solutions than the state-of-the-art algorithms within a reasonable time.

     

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.     

用蚁群算法求解带平衡约束的圆形布局问题

采用启发式方法结合演化算法的思路求解带平衡约束的圆形布局问题.首先对传统优化模型进行调整,并探讨了调整的合理性;然后设计一种分步定位的布局方法,在此基础上利用蚁群算法寻优;最后利用局部搜索技术,在传统模型意义下对布局进行了改进.数值实验表明,算法的性能比目前已有的结果有较大的提高.     

A branch-and-price algorithm for the general case of scheduling parallel machines with a single server

We consider the strongly NP-hard problem of scheduling two-operation non-preemptable jobs on two identical parallel machines. A single server, that can handle at most one job at a time, is available to carry out the first (or setup) operation. The second operation, to be carried out on the same machine but without the server, must be executed immediately after the setup. The objective is to minimize the makespan. We apply a column generation method to a population of partial schedules, in turn generated by some well known heuristics, to achieve effective and efficient solutions. We compare the performance of this method with those proposed earlier and also suggest future work.     

一种基于GPU加速的细粒度并行蚁群算法

为改善蚁群算法对大规模旅行商问题的求解性能,提出一种基于图形处理器(GPU)加速的细粒度并行蚁群算法.将并行蚁群算法求解过程转化为统一计算设备架构的线程块并行执行过程,使得蚁群算法在GPU中加速执行.实验结果表明,该算法能提高全局搜索能力,增大细粒度并行蚁群算法的蚂蚁规模,从而提高了算法的运算速度.     

An effective ant colony optimization algorithm for multi-objective job-shop scheduling with equal-size lot-splitting

This paper proposes several novel hybrid ant colony optimization (ACO)-based algorithms to resolve multi-objective job-shop scheduling problem with equal-size lot splitting. The main issue discussed in this paper is lot-splitting of jobs and tradeoff between lot-splitting costs and makespan. One of the disadvantages of ACO is its uncertainty on time of convergence. In order to enrich search patterns of ACO and improve its performance, five enhancements are made in the proposed algorithms including: A new type of pheromone and greedy heuristic function; Three new functions of state transition rules; A nimble local search algorithm for the improvements of solution quality; Mutation mechanism for divisive searching; A particle swarm optimization (PSO)-based algorithm for adaptive tuning of parameters. The objectives that are used to measure the quality of the generated schedules are weighted-sum of makespan, tardiness of jobs and lot-splitting cost. The developed algorithms are analyzed extensively on real-world data obtained from a printing company and simulated data. A mathematical programming model is developed and paired-samples t-tests are performed between obtained solutions of mathematical programming model and proposed algorithms in order to verify effectiveness of proposed algorithms.