带运输考虑的多阶段动态可重入混合流水车间调度

可重入混合流水车间调度允许一个工件多次进入某些加工阶段,它广泛出现在许多工业制造过程中,如半导体制造、印刷电路板制造等.本文研究了带运输时间的多阶段动态可重入混合流水车间问题,目标是最小化总加权完成时间.针对该问题,建立了整数规划模型,进而基于工件解耦方式提出了两种改进的拉格朗日松弛(LR)算法.在这些算法中,设计了动态规划的改进策略以加速工件级子问题的求解,提出了异步次梯度法以得到有效的乘子更新方向.测试结果说明了所提出的两种改进算法在解的质量和运行时间方面均优于常规LR算法,两种算法都能在可接受的计算时间内得到较好的近优解.     

Hybrid Nested Partitions and Mathematical Programming Approach and Its Applications

Large-scale discrete optimization problems are difficult to solve, especially when different kinds of real constraints are considered. Conventionally, standard mathematical programming is a general approach for discrete optimization, but may suffer from the unacceptable long solution time in applications. On the other hand, some heuristics/metaheuristics methods are more powerful in finding approximate solutions efficiently, but mostly are problem and constraint dependent. In this paper, we develop a new hybrid nested partitions and mathematical programming approach, which creates compliance between mathematical programming and the heuristics/metaheuristics methods. Potentially applicable to many different types of problems, the hybrid approach can provide approximate solutions efficiently, and in the meantime can easily handle different kinds of constraints. The applications of the hybrid approach to the local pickup and delivery problem (LPDP) and the discrete facility location problem (DFLP) are presented in this paper.     

Two-stage hybrid flowshop scheduling with simultaneous processing machines

Simultaneous processing machines, common in processing industries such as steel and food production, can process several jobs simultaneously in the first-in, first-out manner. However, they are often highly energy-consuming. In this paper, we study a new two-stage hybrid flowshop scheduling problem, with simultaneous processing machines at the first stage and a single no-idle machine with predetermined job sequence at the second stage. A mixed integer programming model is proposed with the objective of minimizing the total processing time to reduce energy consumption and improve production efficiency. We give a sufficient and necessary condition to construct feasible sequencing solutions and present an effective approach to calculate the time variables for a feasible sequencing solution. Based on these results, we design a list scheduling heuristic algorithm and its improvement. Both heuristics can find an optimal solution under certain conditions with complexity O(nlogn), where n is the number of jobs. Our experiments verify the efficiency of these heuristics compared with classical heuristics in the literature and investigate the impacts of problem size and processing times.     

Heuristic solutions to the long-term unit commitment problem with cogeneration plants

We consider a long-term version of the unit commitment problem that spans over one year divided into hourly time intervals. It includes constraints on electricity and heating production as well as on biomass consumption. The problem is of interest for scenario analysis in long-term strategic planning. We model the problem as a large mixed integer programming problem. Two solutions to this problem are of interest but computationally intractable: the optimal solution and the solution derived by market simulation. To achieve good and fast approximations to these two solutions, we design heuristic algorithms, including mixed integer programming heuristics, construction heuristics and local search procedures. Two setups are the best: a relax and fix mixed integer programming approach with an objective function reformulation and a combination of a dispatching heuristic with stochastic local search. The work is developed in the context of the Danish electricity market and the computational analysis is carried out on real-life data.     

A hybrid memetic algorithm for maximizing the weighted number of just-in-time jobs on unrelated parallel machines

This paper presents a hybrid memetic algorithm for the problem of scheduling n jobs on m unrelated parallel machines with the objective of maximizing the weighted number of jobs that are completed exactly at their due dates. For each job, due date, weight, and the processing times on different machines are given. It has been shown that when the numbers of machines are a part of input, this problem is NP-hard in the strong sense. At first, the problem is formulated as an integer linear programming model. This model is practical to solve small-size problems. Afterward, a hybrid memetic algorithm is implemented which uses two heuristic algorithms as constructive algorithms, making initial population set. A data oriented mutation operator is implemented so as to facilitate memetic algorithm search process. Performance of all algorithms including heuristics (H1 and H2), hybrid genetic algorithm and hybrid memetic algorithm are evaluated through computational experiments which showed the capabilities of the proposed hybrid algorithm.     

A hybrid genetic algorithm for mixed model assembly line balancing problem with parallel workstations and zoning constraints

In this paper, we propose a hybrid genetic algorithm to solve mixed model assembly line balancing problem of type I (MMALBP-I). There are three objectives to be achieved: to minimize the number of workstations, maximize the workload smoothness between workstations, and maximize the workload smoothness within workstations. The proposed approach is able to address some particular features of the problem such as parallel workstations and zoning constraints. The genetic algorithm may lack the capability of exploring the solution space effectively. We aim to improve its exploring capability by sequentially hybridizing the three well known heuristics, Kilbridge & Wester Heuristic, Phase-I of Moodie & Young Method, and Ranked Positional Weight Technique, with genetic algorithm. The proposed hybrid genetic algorithm is tested on 20 representatives MMALBP-I and the results are compared with those of other algorithms.     

Modeling machine loading problem of FMSs and its solution methodology using a hybrid tabu search and simulated annealing-based heuristic approach

In this article, a machine loading problem of a flexible manufacturing system (FMS) is discussed having the bicriterion objectives of minimizing system unbalance and maximizing throughput in the presence of technological constraints such as available machining time and tool slots. A generic 0–1 integer programming formulation with the objective functions and constraints described above has been proposed. A hybrid algorithm based on tabu search and simulated annealing (SA) is employed to solve the problem. The main advantage of this approach is that a short-term memory provided by the tabu list can be used to avoid revisiting the solution while preserving the stochastic nature of the SA method. The proposed methodology has been tested on ten standard problems and the results obtained are compared with those from some of the existing heuristics.     

Heuristics for the rural postman problem

When addressing the problem of snow removal for secondary roads, a tool for solving the rural postman problem can be very useful. We present some ideas for heuristics for this problem. The heuristics are of the same type as the classical Frederickson heuristic. The ideas concern the order of the main steps in such a method, namely constructing a connected graph with all vertices having even degree, containing all the required edges. We also propose two postprocessing heuristics for improving the tours and removing unnecessary detours. The computational tests show that the ideas are interesting alternatives to the classical approach, and that running times are acceptable. We study problem characteristics that may indicate which method to choose.     

Group-scheduling problems in electronics manufacturing

This paper addresses the flowshop group-scheduling problems typically encountered in the assembly of printed circuit boards in electronics manufacturing. A mathematical programming model is formulated to capture the characteristics inherent to group-scheduling problems experienced in electronics manufacturing as well as those common to a wide range of group-scheduling problems encountered in other production environments. Several heuristics, each incorporating different components that underlie the tabu search concept, are developed to solve this strongly NP-hard problem effectively in a timely manner. In order to investigate the quality of the heuristic solutions with respect to tight lower bounds, an effective and efficient decomposition approach is developed. The problem is decomposed into a master problem and single-machine subproblems, and a column generation algorithm is developed to solve the linear programming relaxation of the master problem. Branching schemes, compatible with the column generation subproblems, are employed to partition the solution space when the solution to the linear programming relaxation is not integral. Furthermore, tabu search based fast heuristics are implemented to solve the subproblems, and an effective stabilization method is developed to accelerate the column generation approach. An experimental design with both fixed and random factors accompanied by rigorous statistical analyses of computational tests conducted on randomly generated test problems as well as on a large size real industry problem confirm the high performance of the proposed approach in identifying quality lower bounds and strongly suggest its flexibility and applicability to a wide range of real problems.     

A new hybrid algorithm for the balanced transportation problem

We propose a heuristic-exact hybrid algorithm that consists of a heuristic phase, based on two novel heuristics, followed by an exact phase, based on an adapted Ford–Fulkerson algorithm, to solve the Balanced Transportation Problem (BTP). First, we propose three alternative primal models for the BTP. We also define the concepts of negative sets, negative dual rectangles, and the optimal tableau for the BTP. Next, we explore the relationships between these concepts. We also propose two greedy heuristics, based on a linear programming relaxation of the BTP model, to find some negative sets and negative dual rectangles. These two heuristics turn out to be very efficient and obtain optimal or near-optimal BTP tableaus rapidly, as confirmed by the computational experiments. Then, an adapted Ford–Fulkerson algorithm is presented and used to find an optimal solution. The two important advantages of our adapted Ford–Fulkerson algorithm over the standard Ford–Fulkerson algorithm are more flexibility and efficiency. Extensive computational results show that the growth in run-time of our hybrid algorithm, on average, is approximately a linear function of the BTP size. It has significant advantage over the transportation simplex method and on the largest problem instances it is almost five times faster. A key feature of the proposed algorithm is that it is free of degeneracy and cycling altogether.     

Randomized local search,evolutionary algorithms,and the minimum spanning tree problem

Randomized search heuristics, among them randomized local search and evolutionary algorithms, are applied to problems whose structure is not well understood, as well as to problems in combinatorial optimization. The analysis of these randomized search heuristics has been started for some well-known problems, and this approach is followed here for the minimum spanning tree problem. After motivating this line of research, it is shown that randomized search heuristics find minimum spanning trees in expected polynomial time without employing the global technique of greedy algorithms.     

Experimental comparison of parametric,non-parametric,and hybrid multigroup classification

This study evaluates the relative performance of some well-known classification techniques, as well as a proposed hybrid method. The proposed hybrid method is a combination of k-nearest neighbor (kNN) and linear programming (LP) method for four group classification. Computational experiments are conducted to evaluate the performances of these classification techniques. Monte Carlo simulation is used to generate dataset with varying characteristics such as multicollinearity, nonlinearity, etc. for the experiments. The experimental results indicate that LP approaches, in general, and the proposed hybrid method, in particular, consistently have lower misclassification rates for most data characteristics. Furthermore, the hybrid method utilizes the strengths of both methods – k-NN and linear programming – resulting in considerable improvement in the classification accuracy. The results of this study can aid in the design of various hybrid techniques that combine the strengths of different methods to improve classification accuracy and reliability.     

Genetic based discrete particle swarm optimization for Elderly Day Care Center timetabling

The timetabling problem of local Elderly Day Care Centers (EDCCs) is formulated into a weighted maximum constraint satisfaction problem (Max-CSP) in this study. The EDCC timetabling problem is a multi-dimensional assignment problem, where users (elderly) are required to perform activities that require different venues and timeslots, depending on operational constraints. These constraints are categorized into two: hard constraints, which must be fulfilled strictly, and soft constraints, which may be violated but with a penalty. Numerous methods have been successfully applied to the weighted Max-CSP; these methods include exact algorithms based on branch and bound techniques, and approximation methods based on repair heuristics, such as the min-conflict heuristic. This study aims to explore the potential of evolutionary algorithms by proposing a genetic-based discrete particle swarm optimization (GDPSO) to solve the EDCC timetabling problem. The proposed method is compared with the min-conflict random-walk algorithm (MCRW), Tabu search (TS), standard particle swarm optimization (SPSO), and a guided genetic algorithm (GGA). Computational evidence shows that GDPSO significantly outperforms the other algorithms in terms of solution quality and efficiency.     

Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times

This research analyzes the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization of the identical parallel processing machines and is closer to real-world production systems. Each machine can accommodate and process several jobs simultaneously as a batch as long as the machine capacity is not exceeded. The batch processing time and the batch ready time are respectively equal to the largest processing time and the largest ready time among all the jobs in the batch. Motivated by the computational complexity and the practical relevance of the problem, we present several heuristics based on first-fit and best-fit earliest job ready time rules. We also present a mixed integer programming model for the problem and a lower bound to evaluate the quality of the heuristics. The small computational effort of deterministic heuristics, which is valuable in some practical applications, is also one of the reasons that motivates this study. The results show that the heuristic proposed in this paper has a superior performance compared to the heuristics based on ideas proposed in the literature.     

Shipment partitioning and routing to minimize makespan in a transportation network

This paper addresses the problem of partitioning and transporting a shipment of known size through an n-node public transportation network with known scheduled departure and arrival times and expected available capacities for each departure. The objective is to minimize the makespan of shipping. The problem while practical in its scope, has received very little attention in the literature perhaps because of the concentration of research in vehicle routing without regard to partitioning and partitioning without regard to routing. A general non-linear programming model is developed. The model is then converted into a linear model through the Routing First and Assignment Second approach. This approach is different from the general decomposition approaches since they normally do not guarantee optimality. However, the linear model still involves a large number of constraints, and solution is not attempted here. Instead, three heuristics are proposed for solving the problem. Two of the heuristics use iterative techniques to evaluate all possible paths. The third heuristic uses a max-flows approach based upon aggregated capacities to reduce the size of the network presented to the other heuristics. This allows for a good starting point for other heuristics, and may impact the total computational effort. We find that the heuristics developed perform well because in the case of networks that are not congested, they find the optimal solution.     

Minimizing makespan in two-stage hybrid cross docking scheduling problem

This paper studies the two-stage hybrid cross docking scheduling problem. In which, the job in the second stage cannot be processed until its precedent subset jobs in the first stage have all been completed and at least one stage contains more than one machine. The objective is to minimize the makespan. Firstly, a mixed integer programming is presented and solved by CPLEX for small scale instances. Secondly, four heuristics are proposed to investigate the performance for moderate and large scale instances. Furthermore, one lower bound is given to compare with the four heuristics. Finally, computational experiments are carefully designed to illustrate and compare these approaches and computational results are reported in detail.     

Scheduling independent tasks on heterogeneous processors using heuristics and Column Pricing

Efficiently scheduling a set of independent tasks on a virtual supercomputer formed by many heterogeneous components has great practical importance, since such systems are commonly used nowadays. Scheduling efficiency can be seen as the problem of minimizing the overall execution time (makespan) of the set of tasks under question. This problem is known to be NP-hard and is currently addressed using heuristics, evolutionary algorithms and other optimization methods. In this paper, firstly, two novel fast executing heuristics, called LSufferage and TPB, are introduced. L(ist)Sufferage is based on the known heuristic Sufferage and can achieve in general better results than it for most of the cases. T(enacious)PB is also based on another heuristic (Penalty Based) and incorporates new ideas that significantly improve the quality of the resulted schedule. Secondly, a mathematical model of the problem is presented alongside with an associated approach based on the Linear Programming method of Column Pricing. This approach, which is called Column Pricing with Restarts (CPR), can be categorized as a hybrid mathematical programming and heuristic approach and is capable of solving in reasonable time problem instances of practically any size. Experiments show that CPR achieves superior results improving over published results on problem instances of various sizes. Moreover, hardware requirements of CPR are minimal.     

An optimization approach for the lot sizing and scheduling problem in the brewery industry

This study considers a production lot sizing and scheduling problem in the brewery industry. The underlying manufacturing process can be basically divided into two main production stages: preparing the liquids including fermentation and maturation inside the fermentation tanks; and bottling the liquids on the filling lines, making products of different liquids and sizes. This problem differs from other problems in beverage industries due to the relatively long lead times required for the fermentation and maturation processes and because the “ready” liquid can remain in the tanks for some time before being bottled. The main planning challenge is to synchronize the two stages (considering the possibility of a “ready” liquid staying in the tank until bottling), as the production bottlenecks may alternate between these stages during the planning horizon. This study presents a novel mixed integer programming model that represents the problem appropriately and integrates both stages. In order to solve real-world problem instances, MIP-based heuristics are developed, which explore the model structure. The results show that the model is able to comprise the problem requirements and the heuristics produce relatively good-quality solutions.     

Solving a fuzzy multi objective model of a production–distribution system using meta-heuristic based approaches

This paper studies a multi-objective production–distribution system. The objectives are to minimize total costs and maximize the reliability of transportations system. Each transportation system is assumed to be of unique reliability. In the real world, some parameters may be of vagueness; therefore, some tools such as fuzzy logic is applied to tackle with. The problem is formulated using a mixed integer programming model. Commercial software can optimally solve small sized instances. We propose two novel HEURISTICS called ranking genetic algorithm (RGA) and concessive variable neighborhood search (CVNS) in order to solve the large sized instances. RGA utilizes various crossover operators and compares their performances so that better crossover operators are used during the solution process. CVNS applies several neighborhood search structures with a novel learning procedure. The heuristics can recognize which neighborhood structure performs well and applies those more than the others. The results indicated that RGA is of higher performance.     

Exact and heuristic algorithms for the just-in-time scheduling problem in a batch processing system

Batch processing systems are commonly used in many different environments such as chemical and semiconductor industries. In this research, a just-in-time scheduling problem in a batch processing system is investigated. Minimization of total earliness and tardiness of the jobs with respect to a common due date is considered as the objective function. First, the research problem is formulated as a mixed integer linear programming model. Then, to find the optimal schedule for a predetermined set of batches, a dynamic programming algorithm is proposed. Based on the proposed dynamic programming algorithm, several heuristics are also developed. A lower bounding method is presented, and then a branch and bound algorithm is proposed to solve the problem optimally. To demonstrate the performance of the proposed algorithms, several computational experiments are conducted.