Due windows group scheduling using an effective hybrid optimization approach

This paper considers the problem of scheduling part families (groups) and jobs within each part family in a hybrid flow shop manufacturing cell with sequence-dependent family setups times where jobs should be completed at times as close as possible to their respective due dates, and hence both earliness and tardiness should be penalized while processing parts (jobs) in each family together. It is assumed that earliness and tardiness penalties will not occur if a job is completed within the due window. The objective is to determine a schedule that minimizes sum of the earliness and tardiness of jobs. To this problem, the hybrid metaheuristic algorithm combined elements from particle swarm optimization; simulated annealing and variable neighborhood search are developed. The aim of using a hybrid metaheuristic is to raise the level of generality so as to be able to apply the same solution method to several problems. Problem sizes ranging in size from small, medium, to large are considered along with three levels of flexibility. The higher the number of stages and the number of parallel machines in each stage, the higher is the flexibility introduced into the problem. A design of experiments approach is employed to calibrate the parameters and operators of the algorithm. We present computational experiments on 126 problems and compare the results with the simulated annealing and genetic algorithms that presented recently. The computational results show that our proposed algorithm is more efficient than the other methods.     

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

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

一类带有deadline约束的作业车间提前/拖期调度问题研究

针对带有零件deadline时间约束的一类作业车间提前/拖期调度问题,设计了一种改进型遗传算法(EGA)。EGA算法采用拖期优先的调度策略,将原有的非正规性能指标的E/T调度问题转化为拖期子问题、修复子问题和提前子问题,以此来降低E/T调度问题的求解复杂度。采用基于工序的编码方法,在染色体解码过程中,分别采用了主动解码、染色体修复和逆向重调度三阶段的解码操作,以期实现在满足零件deadline约束的前提下尽可能降低提前/拖期惩罚总成本。180个调度测试用例仿真结果表明,EGA算法在解决问题数、寻优能力、调度结果的均衡性等方面具有一定的优势。     

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.     

互替机床提前/延期惩罚调度问题的启发式算法

对以作业提前或延期惩罚因素之和最小为目标函数的互替机床调度问题进行了描述，提出和阐述了一种四段式启发式算法，并通过大量不同规模的问题仿真对该算法进行了评价分析，结果表明该算法可行、有效。     

Job shop scheduling based on earliness and tardiness penalties with due dates and deadlines: an enhanced genetic algorithm

This paper studies a job shop scheduling problem with due dates and deadlines in the presence of tardiness and earliness penalties. Due dates are desired completion dates of jobs given by the customer, while deadlines are determined by the manufacturer based on customer due dates. Due dates can be violated at the cost of tardiness, whereas deadlines must be met and cannot be violated. The aforementioned scheduling problem, which is NP-hard, can be formulated with the objective function of minimizing the sum of weighted earliness and weighted tardiness of jobs subject to due dates and deadlines. In order to solve this problem, an enhanced genetic algorithm (EGA) is introduced in this paper. EGA utilizes an operation-based scheme to represent schedules as chromosomes. After the initial population of chromosomes is randomly generated, each chromosome is processed through a three-stage decoder, which first reduces tardiness based on due dates, second ensures deadlines are not violated, and finally reduces earliness based on due dates. After the population size is reached, EGA continues with selection, crossover, and mutation. The proposed algorithm is tested on 180 job shop scheduling problems of varying sizes and its performance is discussed.     

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 and worker assignment problems on hybrid flowshop with cost-related objective function

This paper proposes a colonial competitive algorithm which is improved by variable neighborhood search algorithm for the simultaneous effects of learning and deterioration on hybrid flowshop scheduling with sequence-dependent setup times. By the effects of learning and deterioration, the processing time of a job is determined by position in the sequence and its execution start time. In addition, it is assumed that the processing time of any job depends on the number of workers assigned to the job on a particular stage, and the more workers assigned to a stage, the shorter the job processing time. These additional traits that are added to the scheduling problem coexist in many realistic scheduling situations. This problem consists of two basic questions of job scheduling and worker assignment. Minimization of the earliness, tardiness, makespan, and total worker employing costs is considered as the objective function. To evaluate the performance of the hybrid colonial competitive algorithm, the random key genetic algorithm, immune algorithm, variable neighborhood search, and hybrid simulated annealing metaheuristic presented previously are investigated for comparison purposes, and computational experiments are performed on standard test problems. Results show that our proposed algorithm performs better than the other algorithms for various test problems.     

A hybrid imperialist competitive algorithm for single-machine scheduling problem with linear earliness and quadratic tardiness penalties

In this paper, we study single-machine scheduling problem when each job is considered with linear earliness and quadratic tardiness penalties with no machine idle time. Here the objective is to find the best sequence of jobs in the reasonable time. This model was studied in several researches, and some algorithms were proposed to solve it such as genetic algorithm. As the size of problem increased, such algorithms were not effective and efficient. Hence, we proposed the hybrid imperialist competitive algorithm. The proposed algorithm is based upon the imperialist competitive algorithm and genetic algorithm concepts. This algorithm was tested in problems with different sizes. The results denoted that the hybrid algorithm can solve different size of problem in reasonable time. This procedure showed its efficiency in medium- and large-sized problems as compared with other available methods.     

A block approach to earliness-tardiness scheduling problems

In this paper, we consider a single-machine job scheduling problem where the objective is to minimize the weighted sum of earliness and tardiness (E/T) penalties of jobs. This problem is consistent with the just-in-time (JIT) production. We propose partitioning of permutation into subsequences (blocks) and replacing sets of moves with its representatives, significantly decreasing the size of the searched neighborhood. Some new properties of the problem and compound moves make eliminating “bad” elements and speeding up calculations possible. These properties allow us to propose a new fast local search algorithm based on a tabu search method. Computational experiments are presented and the results show that the algorithm proposed allows us to obtain the best-known results in a short time.     

Minimizing the earliness/tardiness costs on parallel machine with learning effects and deteriorating jobs: a mixed nonlinear integer programming approach

In this study, we introduce a mixed nonlinear integer programming formulation for parallel machine earliness/tardiness (ET) scheduling with simultaneous effects of learning and linear deterioration, sequence-dependent setups, and a common due-date for all jobs. By the effects of learning and linear deterioration, we propose that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. The developed model allows sequence-dependent setups and sequence-dependent early/tardy penalties. The model can easily provide the optimal solution to problems involving about eleven jobs and two machines.     

Hybrid evolutionary algorithm with marriage of genetic algorithm and extremal optimization for production scheduling

This paper presents a hybrid evolutionary algorithm with marriage of genetic algorithm (GA) and extremal optimization (EO) for solving a class of production scheduling problems in manufacturing. The scheduling problem, which is derived from hot rolling production in steel industry, is characterized by two major requirements: (i) selecting a subset of orders from manufacturing orders to be processed; (ii) determining the optimal production sequence under multiple constraints, such as sequence-dependant transition costs, non-execution penalties, earliness/tardiness (E/T) penalties, etc. A combinatorial optimization model is proposed to formulate it mathematically. For its NP-hard complexity, an effective hybrid evolutionary algorithm is developed to solve the scheduling problem through combining the population-based search capacity of GA and the fine-grained local search efficacy of EO. The experimental results with production scale data demonstrate that the proposed hybrid evolutionary algorithm can provide superior performances in scheduling quality and computation efficiency.     

Ant colony system for job shop scheduling with time windows

Scheduling for a job shop production system is an integral aspect of production management. Scheduling operations must minimize stock, waste, and idle time and ensure on-time delivery of goods in a time window problem. In this study, due date is considered as an interval instead of a time point. This study addresses scheduling with a time window of job shop scheduling problem (JSP) and yields a solution that is close to the time window. The total penalty due to earliness and tardiness is minimized. As the problem is NP-hard, a mathematical model of the JSP with a time window is initially constructed, and data are then simulated. Solutions are obtained by ant colony optimization (ACO) programs written in C-language and are compared with the best solution obtained using LINGO 7.0 to determine the efficiency and robustness. Test results indicate that ACO is extremely efficient. Solution time using ACO is less than that using LINGO. Hence, ACO is both effective and efficient, which are two qualities stressed in business management.     

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.     

Group shop scheduling with uncertain data and a general cost objective

In this paper, a stochastic group shop scheduling problem with a due date-related objective is studied. The group shop scheduling problem provides a general formulation including two other shop scheduling problems, the job shop and the open shop. Both job release dates and processing times are assumed to be random variables with known distributions. Moreover, earliness and tardiness of jobs are penalized at different rates. The objective is to minimize the expected maximum completion cost among all jobs. A lower bound on the objective function is proposed, and then, a hybrid approach following a simulation optimization procedure is developed to deal with the problem. An ant colony optimization algorithm is employed to construct good feasible solutions, while a discrete-event simulation model is used to estimate the performance of each constructed solution that, taking into account its lower bound, may improve the best solution found so far. The proposed approach is then evaluated through computational experiments.     

A novel hybrid multi-objective shuffled frog-leaping algorithm for a bi-criteria permutation flow shop scheduling problem

This paper investigates a novel multi-objective model for a permutation flow shop scheduling problem that minimizes both the weighted mean earliness and the weighted mean tardiness. Since a flow shop scheduling problem has been proved to be NP-hard in a strong sense, a new hybrid multi-objective algorithm based on shuffled frog-leaping algorithm (SFLA) and variable neighborhood search (VNS) is devised to find Pareto optimal solutions for the given problem. To validate the performance of the proposed hybrid multi-objective shuffled frog-leaping algorithm (HMOSFLA) in terms of solution quality and diversity level, various test problems are examined. Further, the efficiency of the proposed algorithm, based on various salient metrics, is compared against two well-known multi-objective genetic algorithms: NSGA-II and SPEA-II. Our computational results suggest that the proposed HMOSFLA outperforms the two foregoing algorithms, especially for large-sized problems.     

基于前序基因表达式编程的单机成组调度算法

建立了满足成组技术要求的带有提前/拖期惩罚的单机调度模型,考虑了订单达到时间不同、交货期窗口不同、机器调整时间与工件组加工顺序相关等多种情形;设计了基于基因表达式编程的多层染色体编码方案,将染色体对应于工件的优先规则公式;最后,实现了利用先进的前序基因表达式编程搜索技术求解该问题的算法,并通过实验验证了该算法的可行性和有效性.     

一种求解作业车间JIT调度问题的混合TS/MP算法

作业车间JIT调度属于一类典型的非正规性能指标调度问题,该类问题为每道工序设置了交货期约束,工序的提前或拖期完工均会产生相应的惩罚成本。采用禁忌搜索和数学规划相结合的混合调度方法进行求解。在算法的迭代搜索过程中,首先,由每个个体产生各机器上的工件加工序列,由此松弛了调度模型中的机器能力析取约束,然后,调用数学规划方法来优化各机器的空闲时间和各工序的开工时间。为提高禁忌搜索算法的计算效率,设计了一种包含交换和插入操作的邻域结构产生方案。最后,用JIT调度领域的32个标准测试算例验证了该调度算法的有效性。     

An intelligent hybrid meta-heuristic for solving a case of no-wait two-stage flexible flow shop scheduling problem with unrelated parallel machines

This paper addresses the problem of no-wait two-stage flexible flow shop scheduling problem (NWTSFFSSP) considering unrelated parallel machines, sequence-dependent setup times, probable reworks and different ready times to actualize the problem. The performance measure used in this study is minimizing maximum completion time (makespan). Because of the complexity of addressed problem, we propose a novel intelligent hybrid algorithm [called hybrid algorithm (HA)] based on imperialist competitive algorithm (ICA) which are combined with simulated annealing (SA), variable neighborhood search (VNS) and genetic algorithm (GA) for solving the mentioned problem. The hybridization is carried out to overcome some existing drawbacks of each of these three algorithms and also for increasing the capability of ICA. To achieve reliable results, Taguchi approach is used to define robust parameters' values for our proposed algorithm. A simulation model is developed to study the performance of our proposed algorithm against ICA, SA, VNS, GA and ant colony optimization (ACO). The results of the study reveal the relative superiority of HA studied. In addition, potential areas for further researches are highlighted.