Simultaneous minimization of total tardiness and waiting time variance on a single machine by genetic algorithms

This paper considers a single machine scheduling problem, with the objective of minimizing a linear combination of total tardiness and waiting time variance in which the idle time is not allowed. Minimizing total tardiness is always regarded as one of the most significant performance criteria in practical systems to avoid penalty costs of tardiness, and waiting time variance is an important criterion in establishing quality of service (QoS) in many systems. Each of these criteria is known to be non-deterministic polynomial-time hard (NP-hard); therefore, the linear combination of them is NP-hard too. For this problem, we developed a genetic algorithm (GA) by applying its general structure that further improves the initial population, utilizing some of heuristic algorithms. The GA is shown experimentally to perform well by testing on various instances.     

Reentrant two-stage multiprocessor flow shop scheduling with due windows

Reentrant flow shop scheduling allows a job to revisit a particular machine several times. The topic has received considerable interest in recent years; with related studies demonstrating that particle swarm algorithm (PSO) is an effective and efficient means of solving scheduling problems. By selecting a wafer testing process with the due window problem as a case study, this study develops a farness particle swarm optimization algorithm (FPSO) to solve reentrant two-stage multiprocessor flow shop scheduling problems in order to minimize earliness and tardiness. Computational results indicate that either small- or large-scale problems are involved in which FPSO outperforms PSO and ant colony optimization with respect to effectiveness and robustness. Importantly, this study demonstrates that FPSO can solve such a complex scheduling problem efficiently.     

A scheduling model for serial jobs on parallel machines with different preventive maintenance (PM)

In factories during production, preventive maintenance (PM) scheduling is an important problem in preventing and predicting the failure of machines, and most other critical tasks. In this paper, we present a new method of PM scheduling in two modes for more precise and better machine maintenance, as pieces must be replaced or be repaired. Because of the importance of this problem, we define multi-objective functions including makespan, PM cost, variance tardiness, and variance cost; we also consider multi-parallel series machines that perform multiple jobs on each machine and an aid, the analytic network process, to weight these objectives and their alternatives. PM scheduling is an NP-hard problem, so we use a dynamic genetic algorithm (GA) (the probability of mutation and crossover is changed through the main GA) to solve our algorithm and present another heuristic model (particle swarm optimization) algorithm against which to compare the GA’s answer. At the end, a numerical example shows that the presented method is very useful in implementing and maintaining machines and devices.     

A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks

In simple flow shop problems, each machine operation center includes just one machine. If at least one machine center includes more than one machine, the scheduling problem becomes a flexible flow shop problem (FFSP). Flexible flow shops are thus generalization of simple flow shops. Flexible flow shop scheduling problems have a special structure combining some elements of both the flow shop and the parallel machine scheduling problems. FFSP can be stated as finding a schedule for a general task graph to execute on a multiprocessor system so that the schedule length can be minimized. FFSP is known to be NP-hard. In this study, we present a particle swarm optimization (PSO) algorithm to solve FFSP. PSO is an effective algorithm which gives quality solutions in a reasonable computational time and consists of less numbers parameters as compared to the other evolutionary metaheuristics. Mutation, a commonly used operator in genetic algorithm, has been introduced in PSO so that trapping of solutions at local minima or premature convergence can be avoided. Logistic mapping is used to generate chaotic numbers in this paper. Use of chaotic numbers makes the algorithm converge fast towards near-optimal solution and hence reduce computational efforts further. The performance of schedules is evaluated in terms of total completion time or makespan (C_max). The results are presented in terms of percentage deviation (PD) of the solution from the lower bound. The results are compared with different versions of genetic algorithm (GA) used for the purpose from open literature. The results indicate that the proposed PSO algorithm is quite effective in reducing makespan because average PD is observed as 2.961, whereas GA results in average percentage deviation of 3.559. Finally, influence of various PSO parameters on solution quality has been investigated.     

Bicriteria parallel flow line scheduling using hybrid population-based heuristics

The objective of this paper is to determine a schedule for parallel flow line with bicriteria objective of minimizing the total tardiness and earliness of jobs. An enhancement to its basic greedy randomized adaptive search procedure (GRASP) is used in conjunction with genetic algorithm (GA) and particle swarm optimization (PSO). The feasible solution of GRASP construction phase is used as initial population for both GA and PSO. A number of problems are solved, by varying the number of jobs, lines, and machines, using the hybrid PSO, hybrid GA, PSO, and GA-based methods and the results are compared.     

Parallel machine scheduling with earliness-tardiness penalties and space limits

In order to maximize an availability of machine and utilization of space, the parallel machines scheduling problem with space limit is frequently discussed in the industrial field. In this paper, we consider the parallel machine scheduling problem in which n jobs having different release times, due dates, and space limits are to be scheduled on m parallel machines. The objective function is to minimize the weighted sum of earliness and tardiness. To solve this problem, a heuristic is developed which is divided into three modules hierarchically: job selection, machine selection and job sequencing, and solution improvement. To illustrate its effectiveness, a proposed heuristic is compared with genetic algorithm (GA), hybrid genetic algorithm (HGA), and tabu search (TS), which are well-known meta-heuristics in a large number of randomly generated test problems based on the field situation. Also, we determine the job selection rule that is suitable to the problem situation considered in this paper and show the effectiveness of our heuristic method.     

基于工件聚类的并行机调度算法及其应用

针对纺织生产广泛存在的带工件释放时间、以最小化总拖期工件数和总拖期时间为目标的大规模并行机调度问题,提出一种基于工件聚类的遗传算法。该算法将求解过程分为工件聚类和工件排序两个阶段。在工件聚类阶段,基于影响并行机调度性能的重要调度特征量,采用改进的模糊C-均值聚类方法将所有待上机工件分为多个聚类;在工件排序阶段,采用基于规则编码的遗传算法,优化各聚类内工件的加工顺序。数值计算结果及实际应用效果表明,所提出的算法适用于求解带工件释放时间的大规模并行机调度问题。     

一类并行机调度问题的动态调度算法

针对不确定制造环境中配件数量约束条件发生变化后的并行机动态调度问题,提出了一种基于操作属性模式的并行机动态调度算法.该算法针对总拖期时间性能指标的优化,根据配件负载的裕量和相邻操作的属性模式,对原调度方案的操作次序和操作上机时间进行了调整.在不同操作和设备规模下,以及不同配件数量变化幅度下进行了数值计算.数值计算结果和实际应用结果表明,该算法是有效的,具有计算复杂度低、实时性好、对原调度算法不敏感的特点.     

Minimizing total tardiness for the machine scheduling and worker assignment problems in identical parallel machines using genetic algorithms

The concept of parallel machines has been widely used in manufacturing. This article proposes a genetic algorithm (GA) approach to minimize total tardiness of a set of tasks for identical parallel machines and worker assignment to machines. A spreadsheet-based GA approach is presented to solve the problem. A domain-independent general purpose GA is used, which is an add-in to the spreadsheet software. The paper demonstrates an adaptation of the proprietary GA software to the problem of minimizing total tardiness for the worker assignment scheduling problem for identical parallel machine models. Two 100 I/P/n/m/W problems taken from Hu (Int J Adv Manuf Technol 23:383–388, 2004, Int J Adv Manuf Technol 29:165–169, 2006) for a similar study are simulated. The performance of GA is superior to SES-A/LMC approach used by Hu and very close to the Exhaustive search procedure. It is shown that the spreadsheet GA implementation makes it very easy to adapt the problem for any set of objective measures without changing the actual model. Empirical analysis has been carried out to study the effect of GA parameters, namely, crossover rate, mutation rate, and the population size.     

A hybrid algorithm based on particle swarm optimization and simulated annealing for a periodic job shop scheduling problem

Generating schedules such that all operations are repeated every constant period of time is as important as generating schedules with minimum delays in all cases where a known discipline is desired or obligated by stakeholders. In this paper, a periodic job shop scheduling problem (PJSSP) based on the periodic event scheduling problem (PESP) is presented, which deviates from the cyclic scheduling. The PESP schedules a number of recurring events as such that each pair of event fulfills certain constraints during a given fixed time period. To solve such a hard PJSS problem, we propose a hybrid algorithm, namely PSO-SA, based on particle swarm optimization (PSO) and simulated annealing (SA) algorithms. To evaluate this proposed PSO-SA, we carry out some randomly constructed instances by which the related results are compared with the proposed SA and PSO algorithms as well as a branch-and-bound algorithm. In addition, we compare the results with a hybrid algorithm embedded with electromagnetic-like mechanism and SA. Moreover, three lower bounds (LBs) are studied, and the gap between the found LBs and the best found solutions are reported. The outcomes prove that the proposed hybrid algorithm is an efficient and effective tool to solve the PJSSP.     

Hybrid meta-heuristic algorithm for job shop scheduling with due date time window and release time

This study intends to solve the job shop scheduling problem with both due data time window and release time. The objective is to minimize the sum of earliness time and tardiness time in order to reduce the storage cost and enhance the customer satisfaction. A novel hybrid meta-heuristic which combines ant colony optimization (ACO) and particle swarm optimization (PSO), called ant colony–particle swarm optimization (ACPSO), is proposed to solve this problem. Computational results indicate that ACPSO performs better than ACO and PSO.     

Scheduling in a two-machine flow-shop for earliness/tardiness under learning effect

In the literature, earliness/tardiness (E/T) problem was known as weighted absolute deviation problem, and both tardiness and earliness is very important performance criteria for scheduling problem. While total tardiness criteria provides adaptation for due date (ignoring results of earliness done jobs), it deals with only cost of tardiness. However this phenomenon has been started to change with just-in-time (JIT) production concept. On JIT production, earliness is as important as tardiness. The phenomenon of the learning effect has been extensively studied in many different areas of operational research. However, there have been a few studies in the general context of production scheduling such as flow-shop scheduling. This paper addresses the minimization of the total earliness/tardiness penalties under learning effects in a two-machine flow-shop scheduling problem. Jobs have a common due date. We present mathematical model to obtain an optimal schedule for a given job sequence. We also present heuristics that use genetic algorithm and tabu search, based on proposed properties. Furthermore, random search was used for showing the significance of the study by comparison purpose. A new set of benchmark problems is presented with the purpose of evaluating the heuristics. The experimental results show that the performance of proposed approach is quite well, especially for the instances of large size.     

Parallel processor scheduling for minimizing total weighted tardiness using ant colony optimization

In the modern business environment, meeting due dates and avoiding delay penalties are very important goals that can be accomplished by minimizing total weighted tardiness. We consider a scheduling problem in a system of parallel processors with the objective of minimizing total weighted tardiness. Our aim in the present work is to develop an efficient algorithm for solving the parallel processor problem as compared to the available heuristics in the literature and we propose the ant colony optimization approach for this problem. An extensive experimentation is conducted to evaluate the performance of the ACO approach on different problem sizes with the varied tardiness factors. Our experimentation shows that the proposed ant colony optimization algorithm is giving promising results compared to the best of the available heuristics.     

Ant colony optimization for unrelated parallel machine scheduling

Meeting due dates is a major issue in most manufacturing systems, and one effective measure for due dates is total weighted tardiness. In this research, we consider an ant colony optimization (ACO) algorithm incorporating a number of new ideas (heuristic initial solution, machine reselection step, and local search procedure) to solve the problem of scheduling unrelated parallel machines to minimize total weighted tardiness. The problem is NP-hard in the strong sense, because the single machine case is already NP-hard in the strong sense. Computational results show that the proposed ACO algorithm outperforms other existing algorithms in terms of total weighted tardiness.     

An improved particle swarm optimization for the resource-constrained project scheduling problem

In this paper, an improved particle swarm optimization (PSO) algorithm is proposed for the resource-constrained project scheduling problem (RCPSP) which is widely applied in advanced manufacturing, production planning, and project management. The algorithm treats the solutions of RCPSP as particle swarms and employs a double justification skill and a move operator for the particles, in association with rank-priority-based representation, greedy random search, and serial scheduling scheme, to execute the intelligent updating process of the swarms to search for better solutions. The integration combines and overhauls the characteristics of both PSO and RCPSP, resulting in enhanced performance. The computational experiments are subsequently conducted to set the adequate parameters and compare the proposed algorithm with other approaches. The results suggest that the proposed PSO algorithm augments the performance by 9.26, 16.17, and 10.45 % for the J30, J60, and J120 instances against the best lower bound-based PSO currently available, respectively. Moreover, the proposed algorithms demonstrate obvious advantage over other proposals in exploring solutions for large-scale RCPSP problems such as the J60 and J120 instances.     

并行多机提前/拖期调度的启发式算法

准时制生产模式要求生产任务必须在交货期内完成.实际生产中这一问题受很多约束的影响变得非常复杂.文章针对任务动态到达、任务转换存在的调整时间和交货期、提前/拖期单位成本各不相同的并行多机上任务排序问题进行了分析,设计了一种解决并行多机提前/拖期调度的启发式近似求解算法.大量实验数据和应用实例充分表明文章所提的启发式算法是有效的.     

Sensitivity search for the rescheduling of semiconductor photolithography operations

This study deals with the rescheduling problem of the photolithography area in semiconductor wafer fabrications. The objective is to find a schedule that minimizes the weighted sum of makespan, maximum tardiness, and total setup time. Practical issues such as machine breakdowns, limited number of available masks, restrictions on photoresist, production notice, and machine setup are considered. Three popular search algorithms—simulated annealing (SA), genetic algorithm (GA), and tabu search (TS) — are tested to solve the scheduling problem. We also propose a new sensitivity search approach. A new event changes the scheduling problem. Thus, the problem needs to be re-solved to reflect such changes. In an actual production environment, we propose that, instead of searching for a solution from scratch, the search process can be restarted from the best solution of an original problem that is very similar to the new problem. Using an industrial data set, this study tests the proposed approach. The results show that TS performs the best among the algorithms tested, and the performance of the sensitivity TS significantly surpasses that of the traditional approach.     

Solving a multi-objective job shop scheduling problem with sequence-dependent setup times by a Pareto archive PSO combined with genetic operators and VNS

In this paper, we present a combination of particle swarm optimization (PSO) and genetic operators for a multi-objective job shop scheduling problem that minimizes the mean weighted completion time and the sum of the weighted tardiness/earliness costs, simultaneously. At first, we propose a new integer linear programming for the given problem. Then, we redefine and modify PSO by introducing genetic operators, such as crossover and mutation operators, to update particles and improve particles by variable neighborhood search. Furthermore, we consider sequence-dependent setup times. We then design a Pareto archive PSO, where the global best position selection is combined with the crowding measure-based archive updating method. To prove the efficiency of our proposed PSO, a number of test problems are solved. Its reliability based on some comparison metrics is compared with a prominent multi-objective genetic algorithm (MOGA), namely non-dominated sorting genetic algorithm II (NSGA-II). The computational results show that the proposed PSO outperforms the above MOGA, especially for large-sized problems.     

考虑节能的改进多目标樽海鞘群算法TFT-LCD面板阵列制程调度问题

TFT-LCD面板生产的阵列制程是可重入混合流水车间调度问题,采用一种改进多目标樽海鞘群算法对其进行优化求解。构建以最大完工时间、总拖期时间和总耗能为优化目标的数学规划模型;针对该问题结构特点,对基本多目标樽海鞘群算法进行了一系列改进操作,包括基于升序排列的随机键编码、PS方法解码、基于Lévy飞行的领导者个体位置更新方式,以及外部档案中非支配个体的变邻域搜索操作,并采用田口方法进行算法参数设置;最后通过对基准算例的数值实验,将改进多目标樽海鞘群算法与基本多目标樽海鞘群算法、多目标粒子群优化算法、快速非支配排序遗传算法进行对比,实验结果表明了改进多目标樽海鞘群算法的有效性。     

求解Job shop调度的协同优化算法

针对量子粒子群算法、遗传算法在求解车间调度存在的局部收敛的问题,提出用量子粒子群算法与遗传算法相结合的协同优化方法求解该问题。该算法采用量子粒子群算法与遗传算法的并行搜索结构,通过迁移算子把各个种群联系起来。仿真结果表明,该算法收敛速度快,且具有较高的求解质量。