A bi-objective possibilistic programming model for open shop scheduling problems with sequence-dependent setup times, fuzzy processing times, and fuzzy due dates

We are concerned with an open shop scheduling problem having sequence-dependent setup times. A novel bi-objective possibilistic mixed-integer linear programming model is presented. Sequence-dependent setup times, fuzzy processing times and fuzzy due dates with triangular possibility distributions are the main constraints of this model. An open shop scheduling problem with these considerations is close to the real production scheduling conditions. The objective functions are to minimize total weighted tardiness and total weighted completion times. To solve small-sized instances for Pareto-optimal solutions, an interactive fuzzy multi-objective decision making (FMODM) approach, called TH method proposed by Torabi and Hassini, is applied. Using this method, an equivalent auxiliary single-objective crisp model is obtained and solved optimally by the Lingo software. For medium to large size examples, a multi-objective particle swarm optimization (MOPSO) algorithm is proposed. This algorithm consists of a decoding procedure using a permutation list to reduce the search area in the solution space. Also, a local search algorithm is applied to generate good initial particle positions. Finally, to evaluate the effectiveness of the MOPSO algorithm, the results are compared with the ones obtained by the well-known SPEA-II, using design of experiments (DOE) based on some performance metrics.     

ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times

To date, the topic of unrelated parallel machine scheduling problems with machine-dependent and job sequence-dependent setup times has received relatively little research attention. In this study, a hybrid artificial bee colony (HABC) algorithm is presented to solve this problem with the objective of minimizing the makespan. The performance of the proposed HABC algorithm was evaluated by comparing its solutions to state-of-the-art metaheuristic algorithms and a high performing artificial bee colony (ABC)-based algorithm. Extensive computational results indicate that the proposed HABC algorithm significantly outperforms these best-so-far algorithms. Since the problem addressed in this study is a core topic for numerous industrial applications, this article may help to reduce the gap between theoretical progress and industrial practice.     

Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates

In this paper, we consider an identical parallel machine scheduling problem with sequence-dependent setup times and job release dates. An improved iterated greedy heuristic with a sinking temperature is presented to minimize the maximum lateness. To verify the developed heuristic, computational experiments are conducted on a well-known benchmark problem data set. The experimental results show that the proposed heuristic outperforms the basic iterated greedy heuristic and the state-of-art algorithms on the same benchmark problem data set. It is believed that this improved approach will also be helpful for other applications.     

Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints

This paper presents a novel, two-level mixed-integer programming model of scheduling N jobs on M parallel machines that minimizes bi-objectives, namely the number of tardy jobs and the total completion time of all the jobs. The proposed model considers unrelated parallel machines. The jobs have non-identical due dates and ready times, and there are some precedence relations between them. Furthermore, sequence-dependent setup times, which are included in the proposed model, may be different for each machine depending on their characteristics. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches or optimization tools is extremely difficult. This paper proposes an efficient genetic algorithm (GA) to solve the bi-objective parallel machine scheduling problem. The performance of the presented model and the proposed GA is verified by a number of numerical experiments. The related results show the effectiveness of the proposed model and GA for small and large-sized problems.     

并行机成组调度问题的启发式算法

研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题,提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题,以最小化总拖后时间为优化目标排列工件的加工次序;然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上;最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。     

Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times

In this paper, we discuss a scheduling problem for jobs on identical parallel machines. Ready times of the jobs, precedence constraints, and sequence-dependent setup times are considered. We are interested in minimizing the performance measure total weighted tardiness that is important for achieving good on-time delivery performance. Scheduling problems of this type appear as subproblems in decomposition approaches for large scale job shops with automated transport of the jobs as, for example, in semiconductor manufacturing. We suggest several variants of variable neighborhood search (VNS) schemes for this scheduling problem and compare their performance with the performance of a list based scheduling approach based on the Apparent Tardiness Cost with Setups and Ready Times (ATCSR) dispatching rule. Based on extensive computational experiments with randomly generated test instances we are able to show that the VNS approach clearly outperforms heuristics based on the ATCSR dispatching rule in many situations with respect to solution quality. When using the schedule obtained by ATCSR as an initial solution for VNS, then the entire scheme is also fast and can be used as a subproblem solution procedure for complex job shop decomposition approaches.     

An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup times

This study introduces the problem of minimizing average relative percentage of imbalance (ARPI) with sequence-dependent setup times in a parallel-machine environment. A mathematical model that minimizes ARPI is proposed. Some heuristics, and two metaheuristics, an ant colony optimization algorithm and a genetic algorithm are developed and tested on various random data. The proposed ant colony optimization method outperforms heuristics and genetic algorithm. On the other hand, heuristics using the cumulative processing time obtain better results than heuristics using setup avoidance and a hybrid rule in assignment.     

Makespan minimization for scheduling unrelated parallel machines with setup times

This study considers the problem of scheduling jobs on unrelated parallel machines with machine-dependent and job sequence-dependent setup times. In this study, a restricted simulated annealing (RSA) algorithm which incorporates a restricted search strategy is presented to minimize the makespan. The proposed RSA algorithm can effective reduce the search effort required to find the best neighborhood solution by eliminating ineffective job moves. The effectiveness and efficiency of the proposed RSA algorithm is compared with the basic simulated annealing and existing meta-heuristics on a benchmark problem dataset used in earlier studies. Computational results indicate that the proposed RSA algorithm compares well with the state-of-the-art meta-heuristic for small-sized problems, and significantly outperforms basic simulated annealing algorithm and existing algorithms for large-sized problems.     

Parallel-machine scheduling problems with sequence-dependent setup times using an ACO,SA and VNS hybrid algorithm

This paper proposes a hybrid metaheuristic for the minimization of makespan in scheduling problems with parallel machines and sequence-dependent setup times. The solution approach is robust, fast, and simply structured, and comprises three components: an initial population generation method based on an ant colony optimization (ACO), a simulated annealing (SA) for solution evolution, and a variable neighborhood search (VNS) which involves three local search procedures to improve the population. The hybridization of an ACO, SA with VNS, combining the advantages of these three individual components, is the key innovative aspect of the approach. Two algorithms of a hybrid VNS-based algorithm, SA/VNS and ACO/VNS, and the VNS algorithm presented previously are used to compare with the proposed hybrid algorithm to highlight its advantages in terms of generality and quality for large instances.     

Dynamic programming algorithms for scheduling parallel machines with family setup times

We address the problem of scheduling jobs with family setup times on identical parallel machines to minimize total weighted flowtime. We present two dynamic programming algorithms — a backward algorithm and a forward algorithm — and we identify characteristics of problems where each algorithm is best suited. We also derive two properties that improve the computational efficiency of the algorithms.Scope and purposeWhile most production schedulers must balance conflicting goals of high system efficiency and timely completion of individual jobs, consideration of this conflict is underdeveloped in the scheduling literature. This paper examines a model that incorporates a fundamental cause of the efficiency/timeliness conflict in practice. We propose solution methodologies and properties of an optimal solution for the purpose of exposing insights that may ultimately be useful in research on more complex models.     

A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times

This paper introduces and compares three different formulations of a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The setup is divided into two parts: one that can be performed at any time and another one that is restricted to be performed outside of a given time interval. As a result, the setup time between two jobs is a function of the completion time of the first job. The problem can be formulated as a time-dependent traveling salesman problem, where the travel time between two nodes is a function of the departure time from the first node. We show that the resulting formulation can be strengthened to provide better linear programming relaxation lower bounds. We also introduce several families of valid inequalities which are used within a branch-and-cut algorithm. Computational experiments show that this algorithm can solve some instances with up to 50 jobs within reasonable computing times.     

A hybrid genetic algorithm for parallel machine scheduling with setup times

Journal of Intelligent Manufacturing - This paper addresses the unrelated parallel machine scheduling problem with sequence and machine dependent setup times and machine eligibility constraints....     

A fuzzy-mixed-integer goal programming model for a parallel-machine scheduling problem with sequence-dependent setup times and release dates

This paper presents a new mixed-integer goal programming (MIGP) model for a parallel-machine scheduling problem with sequence-dependent setup times and release dates. Two objectives are considered in the model to minimize the total weighted flow time and the total weighted tardiness simultaneously. Due to the complexity of the above model and uncertainty involved in real-world scheduling problems, it is sometimes unrealistic or even impossible to acquire exact input data. Hence, we consider the parallel-machine scheduling problem with sequence-dependent set-up times under the hypothesis of fuzzy processing time's knowledge and two fuzzy objectives as the MIGP model. In addition, a quite effective and applicable methodology for solving the above fuzzy model are presented. At the end, the effectiveness of the proposed model and the denoted methodology is demonstrated through some test problems.     

A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times

This paper presents a hybrid approach based on the integration between a genetic algorithm (GA) and concepts from constraint programming, multi-objective evolutionary algorithms and ant colony optimization for solving a scheduling problem. The main contributions are the integration of these concepts in a GA crossover operator. The proposed methodology is applied to a single machine scheduling problem with sequence-dependent setup times for the objective of minimizing the total tardiness. A sensitivity analysis of the hybrid approach is carried out to compare the performance of the GA and the hybrid genetic algorithm (HGA) approaches on different benchmarks from the literature. The numerical experiments demonstrate the HGA efficiency and effectiveness which generates solutions that approach those of the known reference sets and improves several lower bounds.     

A two-stage Ant Colony Optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times

This paper addresses the non-preemptive unrelated parallel machine scheduling problem with machine-dependent and sequence-dependent setup times. All jobs are available at time zero, all times are deterministic, and the objective is to minimize the makespan. An Ant Colony Optimization (ACO) algorithm is introduced in this paper and is applied to this NP-hard problem; in particular, the proposed ACO tackles a special structure of the problem, where the ratio of the number of jobs to the number of machines is large (i.e., for a highly utilized set of machines). Its performance is evaluated by comparing its solutions to solutions obtained using Tabu Search and other existing heuristics for the same problem, namely the Partitioning Heuristic and Meta-RaPS. The results show that ACO outperformed the other algorithms.     

A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines,setup times,and dual criteria

This paper considers a flexible flow shop scheduling problem, where at least one production stage is made up of unrelated parallel machines. Moreover, sequence- and machine-dependent setup times are given. The objective is to find a schedule that minimizes a convex sum of makespan and the number of tardy jobs in a static flexible flow shop environment. For this problem, a 0–1 mixed integer program is formulated. The problem is, however, a combinatorial optimization problem which is too difficult to be solved optimally for large problem sizes, and hence heuristics are used to obtain good solutions in a reasonable time. The proposed constructive heuristics for sequencing the jobs start with the generation of the representatives of the operating time for each operation. Then some dispatching rules and flow shop makespan heuristics are developed. To improve the solutions obtained by the constructive algorithms, fast polynomial heuristic improvement algorithms based on shift moves and pairwise interchanges of jobs are applied. In addition, metaheuristics are suggested, namely simulated annealing (SA), tabu search (TS) and genetic algorithms. The basic parameters of each metaheuristic are briefly discussed in this paper. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages and with an optimal solution for small-size problems. We have found that among the constructive algorithms the insertion-based approach is superior to the others, whereas the proposed SA algorithms are better than TS and genetic algorithms among the iterative metaheuristic algorithms.     

顺序依赖的调整时间和拖期的无缝钢管热轧批量调度算法

无缝钢管热轧生产存在一类特殊的顺序依赖机器调整时间,调整时间依赖于相邻轧制批量间的规格切换,与批量间规格呈线性函数关系.针对具有此类调整时间的热轧批量调度问题,进一步考虑交货期要求,探讨了调整时间与交货期之间的性质特征,并以最小化总机器调整时间和最小化总拖期为目标,基于进化算法框架设计了快速重排序邻域搜索多目标算法(f...     

A simulated annealing algorithm approach to hybrid flow shop scheduling with sequence-dependent setup times

One of the scheduling problems with various applications in industries is hybrid flow shop. In hybrid flow shop, a series of n jobs are processed at a series of g workshops with several parallel machines in each workshop. To simplify the model construction in most research on hybrid flow shop scheduling problems, the setup times of operations have been ignored, combined with their corresponding processing times, or considered non sequence-dependent. However, in most real industries such as chemical, textile, metallurgical, printed circuit board, and automobile manufacturing, hybrid flow shop problems have sequence-dependent setup times (SDST). In this research, the problem of SDST hybrid flow shop scheduling with parallel identical machines to minimize the makespan is studied. A novel simulated annealing (NSA) algorithm is developed to produce a reasonable manufacturing schedule within an acceptable computational time. In this study, the proposed NSA uses a well combination of two moving operators for generating new solutions. The obtained results are compared with those computed by Random Key Genetic Algorithm (RKGA) and Immune Algorithm (IA) which are proposed previously. The results show that NSA outperforms both RKGA and IA.     

Flow shop batching and scheduling with sequence-dependent setup times

This paper addresses the flow shop batching and scheduling problem where sequence-dependent family setup times are present and the objective is to minimize makespan. We consider violating the group technology assumption by dividing product families into batches. In order to reduce setup times, inconsistent batches are formed on different machines, which lead to non-permutation schedules. To the best of our knowledge, this is the first time that the splitting of job families into inconsistent batches has been considered in a flow shop system. A tabu search algorithm is developed which contains several neighbourhood functions, double tabu lists and a multilevel diversification structure. Compared to the state-of-the-art meta-heuristics for this problem, the proposed tabu search algorithm achieves further improvement when the group scheduling assumption is dropped. Also, various experiments conducted on the benchmark problem instances confirm the benefits of batching. Therefore, it will be prudent for the practitioners to consider adopting inconsistent batches and non-permutation schedules to improve their operational efficiency within a reasonable amount of computational effort.     

Soft computing for scheduling with batch setup times and earliness-tardiness penalties on parallel machines

A model for scheduling grouped jobs on identical parallel machines is addressed in this paper. The model assumes that a set-up time is incurred when a machine changes from processing one type of component to a different type of component, and the objective is to minimize the total earliness-tardiness penalties. In this paper, the algorithm of soft computing, which is a fuzzy logic embedded Genetic Algorithm is developed to solve the problem. The efficiency of this approach is tested on several groups of random problems and shows that the soft computing algorithm has potential for practical applications in larger scale production systems.