Scheduling of a hub reentrant job shop to minimize makespan

This paper focuses on a hub reentrant shop scheduling problem which is motivated by actual packing production line in the iron and steel industry. There are five operations for processing a job where three operations must be processed on a hub machine, and between any two consecutive operations on the hub machine, two operations must be processed on other two secondary machines, respectively. We mainly consider two types of the problem. The first is basic hub reentrant shop (BHRS) problem where only one machine in each secondary machine center. The second is hybrid hub reentrant shop (HHRS) problem where multiple machines in each secondary machine center. The objective is to minimize the makespan. For BHRS problem, we show that the problem is NP-hard in the strong sense. Some properties are derived for identifying an optimal schedule. Furthermore, a heuristic algorithm is proposed with the worst performance ratio 6:5, and this ratio is demonstrated tight. For HHRS problem, two well-solvable cases are proposed, respectively. Under a split condition, HHRS is equivalent to a two-stage hybrid flow shop problem. The worst case of a class of proposed algorithms is analyzed. The performance ratio is demonstrated relatively with the secondary machine numbers.     

Scheduling flexible job shop problem subject to machine breakdown with route changing and right-shift strategies

In this paper, flexible job shop scheduling problem with machine breakdown is of concern. Considering that there is a limitation in improving robust and stable performance of rescheduling with a single strategy, an approach with multi-strategies is proposed to make the scheduling more robust and stable. First, in prescheduling, a new idle time insertion strategy is put forward. In this new policy, idle time equal to repair time is inserted into an appropriate position of each machine according to the machine's breakdown nature. Second, route changing strategy combined with right-shift policy is proposed to keep the rescheduling as stable and robust as possible. In this policy, whether to right shift or route change is dependent on the cost of archiving robustness and stability. Based on the two strategies, new algorithms dealing with idle time insertion, right-shift scheduling, and route changing scheduling are designed. The computational results show the effectiveness of the new strategies and new algorithms compared with other strategies.     

A two-phase algorithm for multiple-route job shop scheduling problem subject to makespan

Multiple-route job shop scheduling problem (MRJSP) is a generalization of job shop scheduling problem in which each job may have more than one route for its production and the numbers of operations associated to the alternative routes of the job are not necessarily equal. MRJSP is recognized to be extremely difficult because of its combinatorial nature of integer optimization and the large size of the real problem, necessitating the use of heuristic approaches or dispatching rules for its solution. In this paper, mathematical formulation of MRJSP is first presented. Then, a two-phase algorithm is proposed to deal with the two major sub-problems in MRJSP, namely, the route selection and the sequencing sub-problems. In order to evaluate the effectiveness of the proposed algorithm, several problems (in small, medium, and large sizes) are designed and solved using the proposed algorithm. The problems are also solved using some other dispatching rules, and comparisons are provided. The computational results show that the proposed algorithm generates high-quality schedules in a timely fashion.     

A heuristic approach to minimize expected makespan in open shops subject to stochastic processing times and failures

Many real world situations exist where job scheduling is required. This is the case of some entities, machines, or workers who have to execute certain jobs as soon as possible. Frequently what happens is that several workers or machines are not available to perform their activities during some time periods, due to different circumstances. This paper deals with these situations, and considers stochastic scheduling models to study these problems. When scheduling models are used in practice, they have to take into account that some machines may not be working. That temporal lack of machine availability is known as breakdowns, which happen randomly at any time. The times required to repair those machines are also random variables. The jobs have operations with stochastic processing times, their own release times, and there is no precedence between them. Each job is divided into operations and each operation is performed on the corresponding specialized machine. In addition, in the problems considered, the order in which the operations of each job are done is irrelevant. We develop a heuristic approach to solve these stochastic open-shop scheduling problems where random machine breakdowns can happen. The proposed approach is general and it does not depend on the distribution types of the considered random input data. It provides solutions to minimize the expected makespan. Computational experiences are also reported. The results show that the proposed approach gives a solid performance, finding suitable solutions with short CPU times.     

Scheduling flowshops with condition-based maintenance constraint to minimize expected makespan

Flexible job-shop scheduling problem (FJSP) is an extended traditional job-shop scheduling problem, which more approximates to practical scheduling problems. This paper presents a multi-objective genetic algorithm (MOGA) based on immune and entropy principle to solve the multi-objective FJSP. In this improved MOGA, the fitness scheme based on Pareto-optimality is applied, and the immune and entropy principle is used to keep the diversity of individuals and overcome the problem of premature convergence. Efficient crossover and mutation operators are proposed to adapt to the special chromosome structure. The proposed algorithm is evaluated on some representative instances, and the comparison with other approaches in the latest papers validates the effectiveness of the proposed algorithm.     

Flow shop scheduling with deteriorating jobs under dominating machines to minimize makespan

In this paper, we consider an n-job, m-machine flow shop scheduling problem with deteriorating jobs. By deteriorating jobs, we mean jobs whose processing times are an increasing function of their execution starting time. A simple linear deterioration function is assumed. When some dominant relationships between m???1 machines can be satisfied, we show that the makespan minimization problem can be solved in polynomial time.     

Scheduling deteriorating jobs to minimize the makespan on a single machine

Machine scheduling problems with deteriorating jobs have received increasing attention in recent years, mostly focusing on the linear deterioration models. However, if certain maintenance procedures fail to be completed prior to a prespecified deadline, jobs will require extra time for successful accomplishment in some situations. Therefore, this paper addresses a single-machine problem where the objective is to minimize the makespan under the piecewise linear deterioration model. A branch-and-bound algorithm and two heuristic algorithms are provided to search for the optimal solution and near-optimal solutions, respectively. Computational results are also presented to evaluate the performance of the proposed algorithms.     

A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan

This paper studies a hybrid flow shop scheduling problem (hybrid FSSP) with multiprocessor tasks, in which a set of independent jobs with distinct processor requirements and processing times must be processed in a k-stage flow shop to minimize the makespan criterion. This problem is known to be strongly nondeterministic polynomial time (NP)-hard, thus providing a challenging area for meta-heuristic approaches. This paper develops a simulated annealing (SA) algorithm in which three decode methods (list scheduling, permutation scheduling, and first-fit method) are used to obtain the objective function value for the problem. Additionally, a new neighborhood mechanism is combined with the proposed SA for generating neighbor solutions. The proposed SA is tested on two benchmark problems from the literature. The results show that the proposed SA is an efficient approach in solving hybrid FSSP with multiprocessor tasks, especially for large problems.     

基于最小完工期的离散型作业车间调度问题的遗传算法设计

针对离散型生产作业中的车间调度问题,以完工期最小为目标,设计了遗传算法,并利用PB语言编程实现该算法.最后,将该算法应用于某一钢铁公司金工车间的车间调度,并与原调度的结果做了比较,证明了本算法在实际应用中的有效性.     

Scheduling hybrid flowshops with sequence dependent setup times to minimize makespan and maximum tardiness

This article addresses the problem of scheduling hybrid flowshops where the setup times are sequence dependent to minimize makespan and maximum tardiness. To solve such an NP-hard problem, we introduce a novel simulated annealing (SA) with a new concept, called “Migration mechanism”, and a new operator, called “Giant leap”, to bolster the competitive performance of SA through striking a compromise between the lengths of neighborhood search structures. We hybridize the SA (HSA) with a simple local search to further equip our algorithm with a new strong tool to promote the quality of final solution of our proposed SA. We employ the Taguchi method as an optimization technique to extensively tune different parameters and operators of our algorithm. Taguchi orthogonal array analysis is specifically used to pick the best parameters for the optimum design process with the least number of experiments. We established a benchmark to draw an analogy between the performance of SA with other algorithms. Two basically different objective functions, minimization of makespan and maximum tardiness, are taken into consideration to evaluate the robustness and effectiveness of the proposed HSA. Furthermore, we explore the effects of the increase in the number of jobs on the performance of our algorithm to make sure it is effective in terms of both the acceptability of the solution quality and robustness. The excellence and strength of our HSA are concluded from all the results acquired in various circumstances.     

Heuristics to minimize makespan of parallel batch processing machines

Batch-processing machines can process several jobs simultaneously. These machines are commonly used to test Printed Circuit Boards (PCBs). The processing time and the dimensions of the PCB are given. Each batch is formed such that the total size of all the PCBs in the batch does not exceed the machine capacity. The batch processing time is equal to the longest processing time of all the PCBs in the batch. These batch processing machines are expensive and a bottleneck. Scheduling PCBs on these parallel batch processing machines to minimize their makespan is NP-hard. Consequently, we propose several heuristics. The performance of the proposed heuristics is compared to a simulated annealing approach and a commercial solver.     

GRASP to minimize makespan for a capacitated batch-processing machine

This paper presents a Greedy Randomized Adaptive Search Procedure (GRASP) to minimize the makespan of a capacitated batch-processing machine. Given a set of jobs and their processing times and sizes, the objective is to group these jobs into batches and schedule the batches on a single batch-processing machine such that the time taken to complete the last batch of jobs (or makespan) is minimized. The batch-processing machine can process a batch of jobs simultaneously as long as the total size of all the jobs in that batch does not exceed the machine capacity. The batch-processing time is equal to the longest processing time for a job in the batch. It has been shown that the problem under study is non-deterministic polynomial-time hard. Consequently, a GRASP approach was developed. The solution quality of GRASP was compared to other solution approaches such as simulated annealing, genetic algorithm, and a commercial solver through an experimental study. The study helps to conclude that GRASP outperforms other solution approaches, especially on larger problem instances.     

A modified shifting bottleneck heuristic for the reentrant job shop scheduling problem with makespan minimization

This paper proposes a modified shifting bottleneck heuristic (MSBH) for the reentrant job shop scheduling problem (RJSSP) with makespan minimization objective. Recently, the reentrant job shop has come into prominence as a new type of manufacturing shop. The principle characteristic of a reentrant job shop is that a job may visit certain machines more than once during the process flow, whereas in the classic job shop, each job visits a machine only once. The shifting bottleneck heuristic (SBH) is one of the most successful heuristic approaches for the classical job shop scheduling problem, which decomposes the problem into a number of single-machine subproblems. This paper adapts the SBH for the RJSSP and proposes a new sequencing heuristic for the single-machine maximum lateness subproblem considering the reentrant jobs in order to handle large-size RJSSPs. It also uses a subproblem criticality measure that further shortens the implementation time. The proposed MSBH is tested by using instances up to 20 machines and 100 jobs, and it is illustrated that good quality solutions can be obtained in reasonable computational times. A real-life application of the MSBH is also given as a case study to evaluate its performance.     

Scheduling fuzzy job shop with preventive maintenance through swarm-based neighborhood search

Fuzzy job shop scheduling problem with preventive maintenance (FJSSP-PM) is seldom investigated. In this paper, FJSSP-PM with n resumable jobs processed on m machines are considered and an efficient swarm-based neighborhood search (SNS) is proposed, in which an ordered operation-based representation and the decoding procedure incorporating PM are given. Swap operation and binary tournament selection are applied to update the swarm of SNS for the best solutions of the problem. It is also proved that most of possible actual completion times lie in the cut of fuzzy completion time for each job. SNS is finally compared with some methods from literature and computational results demonstrate that SNS has promising advantage on fuzzy scheduling with PM.     

扰动情形下瓶颈利用对作业车间调度的影响

针对瓶颈100%利用后无法应对扰动而造成调度方案无法执行的问题,提出了瓶颈能力释放率和瓶颈能力释放区的概念,研究了瓶颈利用对作业车间调度的影响.在识别瓶颈的基础上,设置瓶颈能力释放率等级;进行瓶颈能力的按级利用,通过遗传算法优化投料次序,输入Plant-Simulation进行模拟仿真,得到各级瓶颈能力释放率的初始调度优化方案;设置机器故障、缓冲、工艺路线更改、交货期变动等随机扰动,对各级初始调度优化方案进行再次模拟仿真,得到随机扰动下各级瓶颈能力释放率的最优调度方案;分析了随机扰动下不同等级的瓶颈能力释放率对作业调度方案的影响.算例结果证实了瓶颈扰动情形下瓶颈100%充分利用并非科学,生成的调度方案鲁棒性差且调度执行结果并非最优的结论.另外,瓶颈非100%有限利用存在最优的瓶颈能力释放率和瓶颈能力释放区,在此释放区之外,过多或过少的瓶颈保护能力对调度方案都有较大的负面影响.     

以成本优化为平台的混流装配线排序

随着客户需求的日益多样化,混流装配线在工业生产中得到越来越多的应用.为了降低混流装配线的闲置和超载现象带来的成本浪费,在分析混流装配线的闲置和超载成本的基础上,提出一种最小化闲置和超载成本的排序模型,并应用粒子群算法来进行优化.优化综合考虑了粒子群算法中惯性权值的关键作用,给出了一种模糊自适应的惯性权值调整方法.最后将优化模型及算法应用到具体的混流装配线,验证了该方法的有效性.这种排序方法可以降低企业的生产成本,从而提高企业的效益,在企业内具有实际的应用价值.     

Single machine group scheduling with general linear deterioration to minimize the makespan

In this paper, we consider a single machine scheduling problem with deteriorating jobs and group technology assumption. By deteriorating jobs and group technology assumption, we mean that the group setup times and job processing times are both increasing functions of their starting times, i.e., group setup times and job processing times are both described by function, which is a general linear function of time. The objective of the scheduling problem is to minimize the makespan. We show that the problem remains solvable in polynomial time when general linear deterioration and group technology are considered simultaneously.     

Scheduling hybrid flow shop with sequence-dependent setup times and machines with random breakdowns

Much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. Furthermore, most scheduling problems which have been discussed in the literature are under the assumption that machines are continuously available. Nevertheless, in most real life industries, a machine can be unavailable for many reasons, such as unanticipated breakdowns, i.e., stochastic unavailability, or due to a scheduled preventive maintenance where the periods of unavailability are known in advance, i.e., deterministic unavailability. This paper deals with the hybrid flow shop scheduling problems in which there are sequence-dependent setup times, commonly known as the SDST, and machines which suffer stochastic breakdown to optimize objectives based on expected makespan. This type of production system is found in industries such as chemical, textile, metallurgical, printed circuit board, and automobile manufacture. With the increase in manufacturing complexity, conventional scheduling techniques for generating a reasonable manufacturing schedule have become ineffective. The genetic algorithm can be used to tackle complex problems and produce a reasonable manufacturing schedule within an acceptable time. This paper describes how we can incorporate simulation into genetic algorithm approach to the scheduling of a SDST hybrid flow shop with machines that suffer stochastic breakdown. An overview of the hybrid flow shops and scheduling under stochastic unavailability of machines are presented. Subsequently, the details of incorporated simulation into genetic algorithm approach are described and implemented. Consequently, the results obtained are analyzed with Taguchi experimental design.     

Algorithms for no-wait flowshops with total completion time subject to makespan

The m-machine no-wait flowshop scheduling problem, with the objective of minimizing total completion time subject to the constraint that makespan has to be less than or equal to a certain value, is addressed in this paper. First, an algorithm is proposed to find an upper bound on the makespan in case the upper bound is not given or unknown. Given the upper bound on makespan, a proposed algorithm (PAL) with five versions L (1, 5, 10, 15, and 20) and a genetic algorithm (GA) are utilized for solving the problem. Furthermore, a dominance relation is established for the case of four machines. The five versions of PAL and GA are evaluated on randomly generated problems with different number of jobs and number of machines. Computational experiments show that the errors of PA1 0, PA15, and PA20 are much smaller than that of GA while the CPU times of PA10, PA15, and PA20 are significantly smaller than that of GA. Therefore, the algorithms PA10, PA15, and PA20 are superior to the GA algorithm.