Two-agent two-machine flowshop scheduling with learning effects to minimize the total completion time

We study a two-agent scheduling problem in a two-machine permutation flowshop with learning effects. The objective is to minimize the total completion time of the jobs from one agent, given that the maximum tardiness of the jobs from the other agent cannot exceed a bound. We provide a branch-and-bound algorithm for the problem. In addition, we present several genetic algorithms to obtain near-optimal solutions. Computational results indicate that the algorithms perform well in either solving the problem or efficiently generating near-optimal solutions.     

A modified teaching–learning-based optimisation algorithm for bi-objective re-entrant hybrid flowshop scheduling

In this paper, a modified teaching–learning-based optimisation (mTLBO) algorithm is proposed to solve the re-entrant hybrid flowshop scheduling problem (RHFSP) with the makespan and the total tardiness criteria. Based on the simple job-based representation, a novel decoding method named equivalent due date-based permutation schedule is proposed to transfer an individual to a feasible schedule. At each generation, a number of superior individuals are selected as the teachers by the Pareto-based ranking phase. To enhance the exploitation ability in the promising area, the insertion-based local search is embedded in the search framework as the training phase for the TLBO. Due to the characteristics of the permutation-based discrete optimisation, the linear order crossover operator and the swap operator are adopted to imitate the interactions among the individuals in both the teaching phase and the learning phase. To store the non-dominated solutions explored during the search process, an external archive is used and updated when necessary. The influence of the parameter setting on the mTLBO in solving the RHFSP is investigated, and numerical tests with some benchmarking instances are carried out. The comparative results show that the proposed mTLBO outperforms the existing algorithms significantly.     

Minimizing the total completion time in a two-machine flowshop problem with time delays

This article proposes to solve the problem of minimizing the total completion time in a two-machine permutation flowshop environment in which time delays between the machines are considered. For this purpose, an enumeration algorithm based on the branch-and-bound framework is developed, which includes new lower and upper bounds as well as dominance rules. The computational study shows that problems with up to 40 jobs can be solved in a reasonable amount of time.     

The distributed permutation flowshop scheduling problem

This paper studies a new generalization of the regular permutation flowshop scheduling problem (PFSP) referred to as the distributed permutation flowshop scheduling problem or DPFSP. Under this generalization, we assume that there are a total of F identical factories or shops, each one with m machines disposed in series. A set of n available jobs have to be distributed among the F factories and then a processing sequence has to be derived for the jobs assigned to each factory. The optimization criterion is the minimization of the maximum completion time or makespan among the factories. This production setting is necessary in today's decentralized and globalized economy where several production centers might be available for a firm. We characterize the DPFSP and propose six different alternative mixed integer linear programming (MILP) models that are carefully and statistically analyzed for performance. We also propose two simple factory assignment rules together with 14 heuristics based on dispatching rules, effective constructive heuristics and variable neighborhood descent methods. A comprehensive computational and statistical analysis is conducted in order to analyze the performance of the proposed methods.     

Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm

This paper deals with a scheduling problem for reentrant hybrid flowshop with serial stages where each stage consists of identical parallel machines. In a reentrant flowshop, a job may revisit any stage several times. Local-search based Pareto genetic algorithms with Minkowski distance-based crossover operator is proposed to approximate the Pareto optimal solutions for the minimization of makespan and total tardiness in a reentrant hybrid flowshop. The Pareto genetic algorithms are compared with existing multi-objective genetic algorithm, NSGA-II in terms of the convergence to optimal solution, the diversity of solution and the dominance of solution. Experimental results show that the proposed crossover operator and local search are effective and the proposed algorithm outperforms NSGA-II by statistical analysis.     

A two-machine flowshop problem with processing time-dependent buffer constraints—An application in multimedia presentations

To have a quality multimedia presentation through networks, its presentation lag needs to be controlled. One way to reduce the lag is to prefetch the media objects before their due dates. This paper explores techniques for optimizing the object sequence in a prefetch-enabled TV-like presentation. An optimal solution is the one with which the presentation lag is minimized. We formulate the problem into a two-machine flowshop scheduling problem with a single chain precedence constraint and a player-side buffer constraint. The player-side buffer is “processing time-dependent” and distinguished from the conventional item-based intermediate buffer constraints discussed in previous flowshop studies. We prove the problem to be strongly NP-hard. A branch and bound algorithm equipped with four lower bounds and an NEH-based upper bound is developed. The simulation results show that the average gaps between the overall lower bounds and the NEH-based upper bound are less than 3% for problems with a large buffer size, and less than 13% for problems with a small buffer size and high density of precedence constraints. For applications where the media objects are delivered through extremely busy servers with which only very restricted CPU resources can be allocated for computation, the CDS-based algorithm provides better sequences than the NEH-based algorithm.     

Minimizing the number of tardy jobs on a proportionate flowshop with general position-dependent processing times

In various real life scheduling systems job processing times vary according to the number of jobs previously processed. The vast majority of studies assume a restrictive functional form to describe job processing times. In this note, we address a scheduling problem with the most general job processing time functions. The machine setting assumed is an m-machine proportionate flowshop, and the objective function is minimum number of tardy jobs. We show that the problem can be formulated as a bottleneck assignment problem with a maximum cardinality constraint. An efficient polynomial time (O(n⁴ log n)) solution is introduced.     

A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application

The assembly flowshop scheduling problem has been addressed recently in the literature. There are many problems that can be modeled as assembly flowshop scheduling problems including queries scheduling on distributed database systems and computer manufacturing. The problem has been addressed with respect to either makespan or total completion time criterion in the literature. In this paper, we address the problem with respect to a due date-based performance measure, i.e., maximum lateness. We formulate the problem and obtain a dominance relation. Moreover, we propose three heuristics for the problem: particle swarm optimization (PSO), Tabu search, and EDD. PSO has been used in the areas of function optimization, artificial neural network training, and fuzzy system control in the literature. In this paper, we show how it can be used for scheduling problems. We have conducted extensive computational experiments to compare the three heuristics along with a random solution. The computational analysis indicates that Tabu outperforms the others for the case when the due dates range is relatively wide. It also indicates that the PSO significantly outperforms the others for difficult problems, i.e., tight due dates. Moreover, for difficult problems, the developed dominance relation helps reduce error by 65%.     

缓冲区有限的流水车间调度问题的启发式算法

针对缓冲区有限的流水车间调度问题,分析了目标函数的特征,及目标函数与工件空闲时间之间的关系,设计开发了启发式算法。算法将以Makespan为目标函数转化成以最小化机器空闲时间为目标函数,并以此为基础构造初始加工序列,再通过贪婪排序与插入寻优消除缓冲区受限约束并寻找问题的近优解。仿真实验结果表明,算法在求解质量和计算时间方面明显优于其他几种排序规则,并体现了目标函数表达式结构的特性及对解的适应性。