Single Machine Scheduling with Time-Dependent Learning Effect and Non-Linear Past-Sequence-Dependent Setup Times

This paper studies a single machine scheduling problem with time-dependent learning and setup times. Time-dependent learning means that the actual processing time of a job is a function of the sum of the normal processing times of the jobs already scheduled. The setup time of a job is proportional to the length of the already processed jobs, that is, past-sequence-dependent (psd) setup time. We show that the addressed problem remains polynomially solvable for the objectives, i.e., minimization of the total completion time and minimization of the total weighted completion time. We also show that the smallest processing time (SPT) rule provides the optimum sequence for the addressed problem.

A Hybrid Estimation of Distribution Algorithm for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times

A hybrid estimation of distribution algorithm (EDA) with iterated greedy (IG) search (EDA-IG) is proposed for solving the unrelated parallel machine scheduling problem with sequence-dependent setup times (UPMSP-SDST). For makespan criterion, some properties about neighborhood search operators to avoid invalid search are derived. A probability model based on neighbor relations of jobs is built in the EDA-based exploration phase to generate new solutions by sampling the promising search region. Two types of deconstruction and reconstruction as well as an IG search are designed in the IG-based exploitation phase. Computational complexity of the algorithm is analyzed, and the effect of parameters is investigated by using the Taguchi method of design-of-experiment. Numerical tests on 1640 benchmark instances are carried out. The results and comparisons demonstrate the effectiveness of the EDA-IG. Especially, the bestknown solutions of 531 instances are updated. In addition, the effectiveness of the properties is also demonstrated by numerical comparisons. © 2014 Chinese Association of Automation.

Identical Machine Scheduling Problem with Sequence-Dependent Setup Times: MILP Formulations Computational Study

This work aims to give a systematic construction of the two families of mixed-integer-linear-programming (MILP) formulations, which are graph- based and sequence-based, of the well-known scheduling problem. Two upper bounds of job completion times are introduced. A numerical test result analysis is conducted with a two-fold objective 1) testing the performance of each solving methods, and 2) identifying and analyzing the tractability of an instance according to the instance structure in terms of the number of machines, of the jobs setup time lengths and of the jobs release date distribution over the scheduling horizon.

A Linear Programming Approach for Parallel Cell Scheduling with Sequence-Dependent Setup Times

In this study, we consider the problem of scheduling a set of jobs with sequence-dependent setup times on a set of parallel production cells. The objective of this study is to minimize the total completion time. We note that total customer demands for each type should be satisfied, and total required production time in each cell cannot exceed the capacity of the cell. This problem is formulated as an integer programming model and an interface is designed to provide integrity between data and software. Mathematical model is tested by both randomly generated data set and real-world data set from a factory that produce automotive components. As a result of this study, the solution which gives the best alternative production schedule is obtained.

Analysis of dispatching rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times

Stochastic dynamic job shop scheduling pro- blem with consideration of sequence-dependent setup times are among the most difficult classes of scheduling problems. This paper assesses the performance of nine dispatching rules in such shop from makespan, mean flow time, maximum flow time, mean tardiness, maximum tardiness, number of tardy jobs, total setups and mean setup time performance measures viewpoint. A discrete event simulation model of a stochastic dynamic job shop manufacturing system is developed for investigation purpose. Nine dispatching rules identified from literature are incorporated in the simulation model. The simulation experiments are conducted under due date tightness factor of 3, shop utilization percentage of 90 % and setup times less than processing times. Results indicate that shortest setup time （SIMSET） rule provides the best performance for mean flow time and number of tardy jobs measures. The job with similar setup and modified earliest due date （JMEDD） rule provides the best performance for make- span, maximum flow time, mean tardiness, maximum tardiness, total setups and mean setup time measures.

No-Wait Flowshops to Minimize Total Tardiness with Setup Times

The m-machine no-wait flowshop scheduling problem is addressed where setup times are treated as separate from processing times. The objective is to minimize total tardiness. Different dispatching rules have been investigated and three were found to be superior. Two heuristics, a simulated annealing (SA) and a genetic algorithm (GA), have been proposed by using the best performing dispatching rule as the initial solution for SA, and the three superior dispatching rules as part of the initial population for GA. Moreover, improved versions of SA and GA are proposed using an insertion algorithm. Extensive computational experiments reveal that the improved versions of SA and GA perform about 95% better than SA and GA. The improved version of GA outperforms the improved version of SA by about 3.5%.

An Improved Ant Colony Algorithm for a Single-machine Scheduling Problem with Setup Times

Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutu- ally independent and available at time zero.The machine processes the jobs sequentially and it is not idle if there is any job to be pro- cessed.The operation of each job cannot be interrupted.The machine cannot process more than one job at a time.A setup time is needed if the machine switches from one type of job to another.The objective is to find an optimal schedule with the minimal total jobs’completion time.While the sum of jobs’processing time is always a constant,the objective is to minimize the sum of setup times.Ant colony optimization(ACO)is a meta-heuristic that has recently been applied to scheduling problem.In this paper we propose an improved ACO-Branching Ant Colony with Dynamic Perturbation(DPBAC)algorithm for the single-machine schedul- ing problem.DPBAC improves traditional ACO in following aspects:introducing Branching Method to choose starting points;im- proving state transition rules;introducing Mutation Method to shorten tours;improving pheromone updating rules and introduc- ing Conditional Dynamic Perturbation Strategy.Computational results show that DPBAC algorithm is superior to the traditional ACO algorithm.

Hybrid Flow Shop with Setup Times Scheduling Problem

The two-stage hybridflow shop problem under setup times is addressed in this paper.This problem is NP-Hard.on the other hand,the studied problem is modeling different real-life applications especially in manufacturing and high performance-computing.Tackling this kind of problem requires the development of adapted algorithms.In this context,a metaheuristic using the genetic algorithm and three heuristics are proposed in this paper.These approximate solutions are using the optimal solution of the parallel machines under release and delivery times.Indeed,these solutions are iterative procedures focusing each time on a particular stage where a parallel machines problem is called to be solved.The general solution is then a concatenation of all the solutions in each stage.In addition,three lower bounds based on the relaxation method are provided.These lower bounds present a means to evaluate the efficiency of the developed algorithms throughout the measurement of the relative gap.An experimental result is discussed to evaluate the performance of the developed algorithms.In total,8960 instances are implemented and tested to show the results given by the proposed lower bounds and heuristics.Several indicators are given to compare between algorithms.The results illustrated in this paper show the performance of the developed algorithms in terms of gap and running time.

Scheduling a three-machine no-wait flowshop with separated setup time

In many practical flowshop production environments, there is no intermediate storage space available to keep partially completed jobs between any two machines. The workflow has to be continuous, implying that the no-wait conditions must be abided, which is typical in steel and plastic production. We discuss the three-machine no-wait flowshop scheduling problem where the setup times are considered as separated from processing times and sequence independent. The scheduling goal is to minimize the total flowtime. An optimal property and two heuristic algorithms for this problem are proposed. Evaluated over a large number of problems, the proposed heuristics are found that they can yield good solutions effectively with low computational complexity, and have more obvious advantage for the large size problem compared with the existing one.

Neighborhood Combination Search for Single-Machine Scheduling with Sequence-Dependent Setup Time

In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm's performance.In this paper,we present an analysis of neighborhood combination search for solv-ing the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness(SMSWT).First,We propose a new neighborhood structure named Block Swap(B1)which can be con-sidered as an extension of the previously widely used Block Move(B2)neighborhood,and a fast incremental evaluation technique to enhance its evaluation efficiency.Second,based on the Block Swap and Block Move neighborhoods,we present two kinds of neighborhood structures:neighborhood union(denoted by B1UB2)and token-ring search(denoted by B1→B2),both of which are combinations of B1 and B2.Third,we incorporate the neighborhood union and token-ring search into two representative metaheuristic algorithms:the Iterated Local Search Algorithm(ILSnew)and the Hybrid Evolutionary Algorithm(HEA_(new))to investigate the performance of the neighborhood union and token-ring search.Exten-sive experiments show the competitiveness of the token-ring search combination mechanism of the two neighborhoods.Tested on the 120 public benchmark instances,our HEA_(new)has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent metaheuristics.We have also tested the HEA,new algorithm with the selected neighborhood combination search to deal with the 64 public benchmark instances of the single-machine scheduling problem with sequence-dependent setup time.HEAnew is able to match the optimal or the best known results for all the 64 instances.In particular,the computational time for reaching the best well-known results for five chal-lenging instances is reduced by at least 61.25%.

Two-Stage Adaptive Memetic Algorithm with Surprisingly Popular Mechanism for Energy-Aware Distributed Hybrid Flow Shop Scheduling Problem with Sequence-Dependent Setup Time

This paper considers the impact of setup time in production scheduling and proposes energy-aware distributed hybrid flow shop scheduling problem with sequence-dependent setup time(EADHFSP-ST)that simultaneously optimizes the makespan and the energy consumption.We develop a mixed integer linear programming model to describe this problem and present a two-stage adaptive memetic algorithm(TAMA)with a surprisingly popular mechanism.First,a hybrid initialization strategy is designed based on the two optimization objectives to ensure the convergence and diversity of solutions.Second,multiple population co-evolutionary approaches are proposed for global search to escape from traditional cross-randomization and to balance exploration and exploitation.Third,considering that the memetic algorithm(MA)framework is less efficient due to the randomness in the selection of local search operators,TAMA is proposed to balance the local and global searches.The first stage accumulates more experience for updating the surprisingly popular algorithm(SPA)model to guide the second stage operator selection and ensures population convergence.The second stage gets rid of local optimization and designs an elite archive to ensure population diversity.Fourth,five problem-specific operators are designed,and non-critical path deceleration and right-shift strategies are designed for energy efficiency.Finally,to evaluate the performance of the proposed algorithm,multiple experiments are performed on a benchmark with 45 instances.The experimental results show that the proposed TAMA can solve the problem effectively.

Time-dependent water permeation behavior of concrete under constant hydraulic pressure

In the present work, a concrete permeability testing setup was designed to study the behavior of hydraulic concrete subjected to constant hydraulic pressure. The results show that when concrete is subjected to high enough constant hydraulic pressure, it will be permeated, and after it reaches its maximum permeation rate, the permeability coefficient will gradually decrease towards a stable value. A time-dependent model of permeability coefficient for concrete subjected to hydraulic pressure is proposed. It is indicated that the decrease of the permeability coefficient with permeation time conforms well to the negative-exponential decrease model.

设备故障下的零空闲多设备工作中心调度

设备故障是车间调度中最为常见的动态事件,易对原生产调度计划造成影响。为保证加工生产在遇到设备故障后能够快速地对原调度方案做出调整,降低设备故障所带来的负面影响,对设备故障下的零空闲多设备工作中心调度问题进行研究。建立了设备故障下考虑调整时间和搬运时间的零空闲多设备工作中心调度模型,优化目标为最小化最大完工时间、搬运次数和系统稳定性;设计NSGA-Ⅱ-V算法用于原调度和重调度的求解;基于NSGA-Ⅱ-V获得的静态调度结果与部分重调度策略的思想,进行设备故障算例测试。测试结果表明,所提模型和算法可较好地处理动态事件为设备故障的零空闲多设备工作中心调度问题。

考虑序列相关准备时间的分布式柔性作业车间调度研究

针对考虑序列相关准备时间的分布式柔性作业车间调度问题,提出以最小化最大完工时间为优化目标的混合整数线性规划模型,并提出一种改进遗传算法。采用基于负荷均衡的种群初始化方法提高初始种群质量,根据问题特性构造6个局部扰动算子,设计多重局部扰动策略提高算法的局部搜索能力。通过扩展柔性作业车间调度基准生成测试算例,使用正交实验确定算法参数。实验结果表明,所提改进策略能够有效提高算法性能,求解结果优于对比算法,验证了调度模型和所提算法的可行性和有效性。

多目标协同正弦优化算法求解分布式流水车间调度问题

针对最小化最大完工时间(makespan)、总拖期以及平均空闲时间的多目标序列相关准备时间分布式流水车间调度问题,本文提出一种多目标协同正弦优化算法(MCSOA).算法主要包括4个核心阶段:在多邻域搜索阶段,提出了基于关键工厂的搜索策略,并通过正弦优化算法控制搜索范围;在破坏重构阶段,设计了一种迭代搜索策略引导个体的进化方向,同时使用正弦优化算法平衡全局开发与局部搜索;在选择阶段,使用非支配排序与参考点的方法筛选优质解,外部档案集用于存储所有非支配解;在协同阶段,设计种群间共享与竞争机制,平衡3个目标的优化.本文通过多目标优化的均匀性、反世代距离和覆盖率3项性能指标验证算法的有效性,并使用非参数检验证明所提出的算法具有显著性优势.

Equilibrium Joining Strategies in the M/M/1 Queues with Setup Times under N-Policy

This paper carries out a game-theoretic analysis of a single-server queueing system with setup times under N-policy by considering both the partially observable and the partially unobservable information scenarios. The server switches off whenever the system becomes empty, and is resumed when the number of customers reaches a certain threshold value. Customers decide whether to join or to balk the system upon arrival based on their available information. The equilibrium joining strategy of customers as well as the systemzs performance measures are derived under different information levels. We find that both Follow-the-Crowd (FTC) and Avoid-the-Crowd (ATC) behaviors exist in our system. Numerical results show that the social welfare is unimodal in the threshold, and is decreasing in the waiting cost.

AN IMPROVED BRANCH-AND-BOUND ALGORITHM TO MINIMIZE THE WEIGHTED FLOWTIME ON IDENTICAL PARALLEL MACHINES WITH FAMILY SETUP TIMES

This article investigates identical parallel machines scheduling with family setup times. The objective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.

On a BMAP/G/1 G-queue with Setup Times and Multiple Vacations

In this paper, we consider a BMAP/G/1 G-queue with setup times and multiple vacations. Arrivals of positive customers and negative customers follow a batch Markovian arrival process （BMAP） and Markovian arrival process （MAP） respectively. The arrival of a negative customer removes all the customers in the system when the server is working. The server leaves for a vacation as soon as the system empties and is allowed to take repeated （multiple） vacations. By using the supplementary variables method and the censoring technique, we obtain the queue length distributions. We also obtain the mean of the busy period based on the renewal theory.

Erratum to:Equilibrium Joining Strategies in the M/M/1 Queues with Setup Times under N-Policy

The article“Equilibrium Joining Strategies in the M/M/1 Queues with Setup Times under N-Policy”unfortunately contained a mistake about the first author’s affiliation.In the original publication of the paper,this affiliation was“Department of Mathematics,Beijing Jiaotong University,Beijing 100044,China”.It should be“School of Economics and Management,University of Chinese Academy of Sciences,Beijing,100190,China”.