共查询到20条相似文献,搜索用时 9 毫秒
1.
This paper deals with the problem of task scheduling in a no-wait flowshop with two batching machines. Each task has to be processed by both machines. All tasks visit the machines in the same order. Batching machines can process several tasks per batch so that all tasks of the same batch start and complete together. The batch processing time for the first machine is equal to the maximal processing time of the tasks in this batch, and for the second machine is equal to the sum of the processing times of the tasks in this batch. We assume that the capacity of any batch on the first machine is bounded, and that when a batch is completed on the first machine it is immediately transferred to the second machine. The aim is to make batching and sequencing decisions that allow the makespan to be minimized. 相似文献
2.
3.
以调度的总流水时间为优化目标, 提出一种混合差分进化算法。 首先, 建立无等待流水车间调度的问题模型,并用快速方法评估总流水时间指标。 其次,采用LPV规则,实现离散问题的连续编码; 用差分进化算法对总流水时间指标执行优化;引入插入邻域和基于pairwise的局部搜索算法, 分别对差分进化算法产生的新个体和差分进化算法的最优解执行邻域搜索, 达到优化目标全局和局部的最优。 最后,通过计算标准算例, 并与其他算法比较, 验证该混合差分进化算法的有效性。 相似文献
4.
Marcelo Seido Nagano Augusto Almeida da Silva Luiz Antonio Nogueira Lorena 《Engineering Applications of Artificial Intelligence》2012,25(6):1114-1120
This paper addresses the m-machine no-wait flow shop problem where the set-up time of a job is separated from its processing time. The performance measure considered is the total flowtime. A new hybrid metaheuristic Genetic Algorithm–Cluster Search is proposed to solve the scheduling problem. The performance of the proposed method is evaluated and the results are compared with the best method reported in the literature. Experimental tests show superiority of the new method for the test problems set, regarding the solution quality. 相似文献
5.
《Expert systems with applications》2014,41(8):3628-3633
This paper examines the m machine no-wait flow shop problem with setup times of a job separated from its processing time. The performance measure considered is the makespan. The hybrid metaheuristic Evolutionary Cluster Search (ECS_NSL) proposed in Nagano et al. (2012) is extended to solve the scheduling problem. The ECS_NSL performance is evaluated and the results are compared with the best method reported in the literature. Experimental tests show superiority of the ECS_NSL regarding the solution quality. 相似文献
6.
7.
8.
The no-wait flow shop scheduling problem (NWFSSP) performs an important function in the manufacturing industry. Inspired by the overall process of teaching-learning, an extended framework of meta-heuristic based on the teaching-learning process is proposed, which consists of four parts, i.e. previewing before class, teaching phase, learning phase, reviewing after class. This paper implements a hybrid meta-heuristic based on probabilistic teaching-learning mechanism (mPTLM) to solve the NWFSSP with the makespan criterion. In previewing before class, an initial method that combines a modified Nawaz-Enscore-Ham (NEH) heuristic and the opposition-based learning (OBL) is introduced. In teaching phase, the Gaussian distribution is employed as the teacher to guide learners to search more promising areas. In learning phase, this paper presents a new means of communication with crossover. In reviewing after class, an improved speed-up random insert local search based on simulated annealing (SA) is developed to enhance the local searching ability. The computational results and comparisons based on Reeves, Taillard and VRF’s benchmarks demonstrate the effectiveness of mPTLM for solving the NWFSSP. 相似文献
9.
针对NP-难的最小化时间表长为目标的无等待流水车间调度问题,将此问题转化为旅行商问题.采用蚁群优化求得初始工件排序.在提出的一种新的邻域结构基础上,迭代进行集中和分散的变邻域搜索以改善解.用Rec系列及he11和he12共计23个Benchmark算例进行计算验证,并与RAJ算法进行了比较.结果表明所提出的方法是有效的. 相似文献
10.
11.
Nowadays, distributed scheduling problem is a reality in many companies. Over the last years, an increasingly attention has been given to the distributed flow shop scheduling problem and the addition of constraints to the problem. This article introduces the distributed no-wait flow shop scheduling problem with sequence-dependent setup times and maintenance operations to minimize makespan. A mixed-integer linear programming (MILP) is to mathematically describe the problem and heuristic procedures to incorporate maintenance operations to job scheduling are proposed. An Iterated Greedy with Variable Search Neighborhood (VNS), named IG_NM, is proposed to solve small and large instances with size of 4,800 and 13,200 problems, respectively. Computational experiments were conducted to evaluate the performance of IG_NM in comparison with MILP and the most recent methods of literature of distributed flow shop scheduling problems. Statistical results show that in the trade-off between effectiveness and efficiency the proposed IG_NM outperformed other metaheuristics of the literature. 相似文献
12.
E. Dhouib J. Teghem T. Loukil 《International Transactions in Operational Research》2013,20(2):213-232
This paper considers the permutation flow shop scheduling problem with minimal and maximal time lags. Time lags are defined as intervals of time that must exist between every pair of consecutive operations of a job. The objective is to hierarchically minimize two criteria, the primary criterion is the minimization of the number of tardy jobs and the secondary one minimizes the makespan. We propose a mixed integer mathematical programming formulation which can be solved with the subroutine CPLEX. We also propose several versions of simulated annealing algorithm to heuristically solve the problem. Computational experiments to compare the proposed procedures are presented and discussed. 相似文献
13.
针对既存在阻塞限制工件又存在无等待约束工件的柔性流水车间调度问题, 提出了一种离散粒子群优化的求解方法。该方法采用基于排列的编码形式, 设计了推进—迭代算法进行解码并计算问题目标值, 利用离散粒子群优化算法进行全局优化, 利用迭代贪婪(iterated greedy, IG)算法提高种群个体的局部搜索能力。此外, 根据问题特点, 提出最早释放优先(first release first, FRF)和最早完工优先(first complete first, FCF)两种机器分配策略。仿真结果表明, 所提出的方法求解混合约束下柔性流水车间调度问题是可行的、有效的。 相似文献
14.
The flow shop scheduling problem is an attractive subject in the field of scheduling, which has attracted the attention of many researchers in the past five decades. In this paper, the non-permutation flow shop scheduling problem with the learning effects and machine availability constraints has been studied for minimizing the total flow time as a performance measure. First, a mixed integer linear programming model has been proposed for the modeling of the problem and then, an effective improving heuristic method, which is able to find proper non-permutation solutions, has been presented. Finally, the computational results are used for evaluation the performance and effectiveness of the proposed heuristic. 相似文献
15.
Deming Lei 《Computers & Industrial Engineering》2010,58(4):610-617
This paper presents the fuzzy job shop scheduling problem with availability constraints. The objective is to find a schedule that maximizes the minimum agreement index subject to periodic maintenance, non-resumable jobs and fuzzy due-date. A random key genetic algorithm (RKGA) is proposed for the problem, in which a novel random key representation, a new decoding strategy incorporating maintenance operation and discrete crossover (DX) are used. RKGA is applied to some fuzzy scheduling problem with availability constraints and compared with other algorithms. Computational results show that RKGA performs better than other algorithms. 相似文献
16.
17.
No-wait flow shop production has been widely applied in manufacturing, where no waiting time is allowed between intermediate operations. However, minimization of makespan for no-wait flow shop production is NP-hard. In this paper, we propose an average idle time (AIT) heuristic to minimize makespan in no-wait flow shop production. First, we take the current idle times and future idle times into consideration, proposing an initial sequence algorithm, and then use the insertion and neighborhood exchanging methods to further improve solutions. Compared with three existing best-known heuristics, our AIT heuristic can achieve the smallest deviations of 0.23% from optimum, based on Taillard’s benchmarks and 600 randomly generated instances, in the same computational complexity. 相似文献
18.
This paper describes a hybrid tabu search algorithm dedicated to a job shop problem with a no-wait constraint with a makespan criterion. The proposed here algorithm complexity is that the superior algorithm based on the tabu search technique selects parameters controlling the work of a certain constructional algorithm. This approach limits the checked solutions only to a group of solutions being able to be generated by the structural algorithm in question. It bears serious consequences both positive, for example it limits the research scope for a small fraction of relatively extremely well quality of acceptable solutions, and negative that is the lack of possibility of finding the optimal solution. In this paper numerical researches of the proposed algorithm are conducted as well as a comparative analysis with reference to the literature algorithms of the algorithm in question is made. 相似文献
19.
Most of the literature on scheduling assumes that machines are always available. However, in real life industry, machines may be subject to some unavailability periods due to maintenance activities such as breakdowns (stochastic case) and preventive maintenance (deterministic case). In this paper we investigate the two-stage hybrid flow shop scheduling problem with only one machine on the first stage and m machines on the second stage to minimize the makespan. We consider that each machine is subject to at most one unavailability period. The start time and the end time of each period are known in advance (deterministic case) and only the non-resumable case is studied. First we discuss the complexity of the problem. Afterwards, we give the Branch and Bound model for this problem. Last, we calculate the worst-case performances of three heuristics: LIST algorithm, LPT algorithm and H-heuristic. 相似文献
20.
Hall et al. (J. Sched. 2002; 5:307–327) investigated the cycle time minimization problem in a two-machine job shop, where each job consists of at most three
operations. In this note, we reduce the problem to a two-machine reentrant flow shop problem and briefly discuss some consequences. 相似文献