混合Flowshop双目标调度问题的双向仿真方法

针对JIT生产方式的混合Flowshop系统双目标调度问题，提出一种基于前向和反向仿真组合的双向仿真调度方法。用启发式算法进行前向仿真获得工件离开系统的时刻，并将其作为反向仿真的开工时刻。按工件的反向路由（加工顺序）进行反向仿真，以获得工件正向进入系统的较好时刻，从而减少工件的等待和平均的flowtime。仿真结果表明，该方法 能够较好地解决混合Flowshop的双目标调度问题。     

Comments on “A bicriteria flowshop scheduling problem with setup times”

The aim of this paper is to point out that the integer programming model proposed by Eren and Güner [T. Eren, E. Güner, A bicriteria flowshop scheduling problem with setup times, Appl. Math. Comput. 183 (2006) 1292-1300] is incorrect. We propose a new integer programming model for the same scheduling problem based on their model.     

Minimizing makespan with multiple-orders-per-job in a two-machine flowshop

We investigate a new scheduling problem, multiple-orders-per-job (MOJ), in the context of a two-machine flowshop. Lower bounds for the makespan performance measure are provided for combinations of lot-processing and item-processing machines. An optimization model is presented that addresses both job formation and job sequencing. We define a heuristic to minimize the makespan for the MOJ problem for two-machine item-processing flowshops. The heuristic obtains solutions within 2% of a tight lower bound and runs in O(HF) time, where H is the number of orders and F is the restricted number of jobs.     

Johnson’s rule,composite jobs and the relocation problem

Two-machine flowshop scheduling to minimize makespan is one of the most well-known classical scheduling problems. Johnson’s rule for solving this problem has been widely cited in the literature. We introduce in this paper the concept of composite job, which is an artificially constructed job with processing times such that it will incur the same amount of idle time on the second machine as that incurred by a chain of jobs in a given processing sequence. This concept due to Kurisu first appeared in 1976 to deal with the two-machine flowshop scheduling problem involving precedence constraints among the jobs. We show that this concept can be applied to reduce the computational time to solve some related scheduling problems. We also establish a link between solving the two-machine flowshop makespan minimization problem using Johnson’s rule and the relocation problem introduced by Kaplan. We present an intuitive interpretation of Johnson’s rule in the context of the relocation problem.     

A hybrid genetic local search algorithm for the permutation flowshop scheduling problem

Traditionally, the permutation flowshop scheduling problem (PFSP) was with the criterion of minimizing makespan. The permutation flowshop scheduling problem to minimize the total flowtime has attracted more attention from researchers in recent years. In this paper, a hybrid genetic local search algorithm is proposed to solve this problem with each of both criteria. The proposed algorithm hybridizes the genetic algorithm and a novel local search scheme that combines two local search methods: the Insertion Search (IS) and the Insertion Search with Cut-and-Repair (ISCR). It employs the genetic algorithm to do the global search and two local search methods to do the local search. Two local search methods play different roles in the search process. The Insertion Search is responsible for searching a small neighborhood while the Insertion Search with Cut-and-Repair is responsible for searching a large neighborhood. Furthermore, the orthogonal-array-based crossover operator is designed to enhance the GA’s capability of intensification. The experimental results show the advantage of combining the two local search methods. The performance of the proposed hybrid genetic algorithm is very competitive. For the PFSP with the total flowtime criterion, it improved 66 out of the 90 current best solutions reported in the literature in short-term search and it also improved all the 20 current best solutions reported in the literature in long-term search. For the PFSP with the makespan criterion, the proposed algorithm also outperforms the other three methods recently reported in the literature.     

Single-machine and two-machine flowshop scheduling with general learning functions

We show that the O(n log n) (where n is the number of jobs) shortest processing time (SPT) sequence is optimal for the single-machine makespan and total completion time minimization problems when learning is expressed as a function of the sum of the processing times of the already processed jobs. We then show that the two-machine flowshop makespan and total completion time minimization problems are solvable by the SPT sequencing rule when the job processing times are ordered and job-position-based learning is in effect. Finally, we show that when the more specialized proportional job processing times are in place, then our flowshop results apply also in the more general sum-of-job-processing-times-based learning environment.     

求解混合Flowshop调度问题的简化禁忌搜索方案

针对 HFS系统的最小化 Makespan调度问题 ,提出一种禁忌算法和优先级规则相结合的方案 :采用改进的 RA算法对第 1级工件进行排序 ,并用禁忌搜索对其进行优化 ;采用 FAM算法给工件分配设备 ,其他级工件的排序采用最大剩余时间优先级规则 .和其他 HFS的局部搜索算法相比 ,该方案大大缩减了搜索空间 .仿真结果表明 ,该方法能够较好地解决 HFS调度问题 .     

Notes on “A bicriteria flowshop scheduling with a learning effect”

The aim of this paper is to point out that the integer programming model proposed by Eren and Güner [T. Eren, E. Güner, A bicriteria flowshop scheduling with a learning effect, Applied Mathematical Modelling 32 (2008) 1719–1733] is incorrect. We propose a mixed 0–1 programming model for the same scheduling problem based on their model.     

An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives

Iterated Greedy (IG) algorithms are based on a very simple principle, are easy to implement and can show excellent performance. In this paper, we propose two new IG algorithms for a complex flowshop problem that results from the consideration of sequence dependent setup times on machines, a characteristic that is often found in industrial settings. The first IG algorithm is a straightforward adaption of the IG principle, while the second incorporates a simple descent local search. Furthermore, we consider two different optimization objectives, the minimization of the maximum completion time or makespan and the minimization of the total weighted tardiness. Extensive experiments and statistical analyses demonstrate that, despite their simplicity, the IG algorithms are new state-of-the-art methods for both objectives.     

Comments on “A bicriteria m-machine flowshop scheduling with sequence-dependent setup times”

The purpose of this paper is to point out that the programming model proposed by Eren [A bicriteria m-machine flowshop scheduling with sequence-dependent setup times, Appl. Math. Model. 34 (2010) 284–293] is incorrect. We propose a mixed 0–1 programming model for the same scheduling problem based on their model.