A two-stage stochastic programming for single yard crane scheduling with uncertain release times of retrieval tasks

Nowadays maritime transportation has become the mainstream of the global logistics, and the operational efficiency of container terminals plays a critical role in maritime transportation. As one of the most important terminal operational issues, yard crane scheduling that handles both storage and retrieval tasks has caught a lot of interest. However, the uncertainty on the release times of retrieval tasks, as one common phenomenon in daily operations, has been ignored in the literature. This paper investigates single yard crane scheduling to minimise the expected total tardiness of tasks, and focus on the case with uncertain release times of retrieval tasks. A two-stage stochastic programming model is proposed, and the sample average approximation (SAA) approach is applied to solve small instances of the problem. For large-scale instances, a genetic algorithm (GA) and a rule-based heuristic are developed. To evaluate the performances of the solution methods, numerical experiments with 300 instances are implemented. Computational results show that the rule-based heuristic outperforms both GA and SAA in terms of solution quality and running time.     

Single machine scheduling problem with batch setups involving positional deterioration effects and multiple rate-modifying activities

This article considers a single machine scheduling problem with batch setups, positional deterioration effects, and multiple optional rate-modifying activities to minimize the total completion time. This problem is formulated as an integer quadratic programming problem. In view of the complexity of optimally solving this problem, a two-phase heuristic algorithm is proposed where an optimal but non-integer solution is obtained in the first phase by solving a continuous relaxed version of the problem. This solution serves as a lower bound for the optimal value of the total completion time. The second phase of the algorithm generates an integer solution using a simple rounding scheme that is optimum or very close to optimum for this problem. Empirical evaluation and comparison with an existing heuristic algorithm show that the proposed heuristic algorithm is substantially more effective in solving large-size problem instances.     

Scenario-based heuristic to two-stage stochastic program for the parallel machine ScheLoc problem

Scheduling-Location (ScheLoc) problem is a new and interesting topic in manufacturing, considering location and scheduling decisions simultaneously. Most existing works focus on the deterministic problems. In practice, however, job-processing times are usually uncertain due to some factors. This paper investigates the stochastic parallel machine ScheLoc problem to minimise the weighted sum of the location cost and the expectation of the total completion time. A two-stage stochastic programming formulation is proposed, then the sample average approximation (SAA) method is adapted to solve the small-size problems. To efficiently address the large-scale problems, a genetic algorithm (GA) and a scenario-based heuristic are designed. Numerical experiments on 450 instances are conducted. Computational results show that the scenario-based heuristic outperforms SAA method and GA in terms of solution quality and computational time.     

An efficient local search heuristic for the double row layout problem with asymmetric material flow

The double row layout problem (DRLP) consists of arranging a number of rectangular machines of varying widths on either side of a corridor to minimize the total cost of material handling for products that move between these machines. This problem arises in the context of many production environments, most notably semiconductor manufacturing. Because the DRLP contains both combinatorial and continuous aspects, traditional solution approaches are not well suited to obtain solutions within a reasonable time. Moreover, previous approaches to this problem did not consider asymmetric flows. In this paper, an effective local search procedure featuring linear programming is proposed for solving the DRLP with asymmetric flows (symmetric flows being a special case). This approach is compared against several constructive heuristics and solutions obtained by a commercial mixed integer linear programming solver to evaluate its performance. Computational results show that the proposed heuristic is an effective approach, both in terms of solution quality and computational effort.     

Cultural algorithms,an alternative heuristic to solve the job shop scheduling problem

In this work, an approach for solving the job shop scheduling problem using a cultural algorithm is proposed. Cultural algorithms are evolutionary computation methods that extract domain knowledge during the evolutionary process. Additional to this extracted knowledge, the proposed approach also uses domain knowledge given a priori (based on specific domain knowledge available for the job shop scheduling problem). The proposed approach is compared with respect to a Greedy Randomized Adaptive Search Procedure (GRASP), a Parallel GRASP, a Genetic Algorithm, a Hybrid Genetic Algorithm, and a deterministic method called shifting bottleneck. The cultural algorithm proposed in this article is able to produce competitive results with respect to the two approaches previously indicated at a significantly lower computational cost than at least one of them and without using any sort of parallel processing.     

Minimising makespan on a single batch processing machine with dynamic job arrivals and non-identical job sizes

Batch scheduling is a prevalent policy in many industries such as burn-in operations in semiconductor manufacturing and heat treatment operations in metalworking. In this paper, we consider the problem of minimising makespan on a single batch processing machine in the presence of dynamic job arrivals and non-identical job sizes. The problem under study is NP-hard. Consequently, we develop a number of efficient construction heuristics. The performance of the proposed heuristics is evaluated by comparing their results to two lower bounds, and other solution approaches published in the literature, namely the first-fit longest processing time-earliest release time (FFLPT-ERT) heuristic, hybrid genetic algorithm (HGA), joint genetic algorithm and dynamic programming (GA+DP) approach and ant colony optimisation (ACO) algorithm. The computational experiments demonstrate the superiority of the proposed heuristics with respect to solution quality, especially for the problems with small size jobs. Moreover, the computational costs of the proposed heuristics are very low.     

A divide-and-conquer strategy with particle swarm optimization for the job shop scheduling problem

An optimization algorithm based on the ‘divide-and-conquer’ methodology is proposed for solving large job shop scheduling problems with the objective of minimizing total weighted tardiness. The algorithm adopts a non-iterative framework. It first searches for a promising decomposition policy for the operation set by using a simulated annealing procedure in which the solutions are evaluated with reference to the upper bound and the lower bound of the final objective value. Subproblems are then constructed according to the output decomposition policy and each subproblem is related to a subset of operations from the original operation set. Subsequently, all these subproblems are sequentially solved by a particle swarm optimization algorithm, which leads directly to a feasible solution to the original large-scale scheduling problem. Numerical computational experiments are carried out for both randomly generated test problems and the real-world production data from a large speed-reducer factory in China. Results show that the proposed algorithm can achieve satisfactory solution quality within reasonable computational time for large-scale job shop scheduling problems.     

钢铁企业副产煤气优化调度问题模型及算法

考虑钢铁企业副产煤气优化调度问题,在分析问题特征的基础上,建立了数学规划模型。针对模型特点,将遗传算法与混沌理论相结合进行模型求解,在初始种群中引入基于启发式规则生成的优良个体来提高收敛速度;通过建立个体精英库防止最优值的丢失;引入基于混沌序列的邻域搜索以提高算法的寻优效率。通过仿真实验验证了模型与算法的可行性和有效性。     

Lagrangian relaxation method for price-based unit commitment problem

The unit commitment problem consists of determining the schedules for power generating units and the generating level of each unit. The decisions concern which units to commit during each time period and at what level to generate power to meet the electricity demand. The problem is a typical scheduling problem in an electric power system. The electric power industry is undergoing restructuring and deregulation. This article developes a stochastic programming model which incorporates power trading. The uncertainty of electric power demand or electricity price are incorporated into the unit commitment problem. It is assumed that demand and price uncertainty can be represented by a scenario tree. A stochastic integer programming model is proposed in which the objective is to maximize expected profits. In this model, on/off decisions for each generator are made in the first stage. The approach to solving the problem is based on Lagrangian relaxation and dynamic programming.     

原油处理过程短期生产计划优化

在原油处理过程短期生产计划的递阶求解方法中,原油处理短期生产计划问题分为上下两层,上层根据市场需求产生一个目标炼油计划;在此基础上,下层得到一个详细生产计划以实现目标炼油计划。研究了在上层目标炼油计划已知的情况下,下层详细生产计划的求解问题。为该问题建立了基于离散时间表示的混合整数线性规划模型,分析了问题的特点并将其进行转化,给出了基于启发式的求解方法,在保证目标炼油计划实现的前提下,对原油转运过程中油品切换及不同油品的罐底混合进行了优化,取得了一定的成果。用一个工业实例验证了启发式规则的可行性和有效性。     

A priority rule-based constructive heuristic and an improvement method for balancing assembly lines with parallel multi-manned workstations

Assembly lines of big-size products such as buses, trucks and helicopters are very different from the lines studied in the literature. These products’ manufacturing processes have a lot of tasks most of which have long task times. Since traditional assembly line models including only one worker in each station (i.e. simple assembly lines) or at most two workers (two-sided assembly lines) may not be suitable for manufacturing these type of products, they need much larger shop floor for a number of stations and long product flow times. In this study, an assembly line balancing problem (ALBP) with parallel multi-manned stations is considered. Following the problem definition, a mixed integer programming formulation is developed. A detailed study of priority rules for simple ALBPs is also presented, and a new efficient constructive heuristic algorithm based on priority rules is proposed. In order to improve solutions found by the constructive heuristic, a genetic algorithm-based solution procedure is also presented. Benchmark instances in the literature are solved by using the proposed mathematical programming formulation. It has been seen that only some of the small-size instances can be solved optimally by this way. So the efficiency of the proposed heuristic method is verified in small-size instances whose optimal solutions are found. For medium- and big-size instances, heuristics’ results and CPU times are demonstrated. A comparative evaluation with a branch and bound algorithm that can be found in the literature is also carried out, and results are presented.     

A genetic algorithm for solving the economic lot scheduling problem in flow shops

In this study, we propose a hybrid genetic algorithm (HGA) to solve the economic lot scheduling problem in flow shops. The proposed HGA utilizes a so-called Proc PLM heuristic that tests feasibility for the candidate solutions obtained in the evolutionary process of genetic algorithm. When a candidate solution is infeasible, we propose to use a binary search heuristic to ‘fix’ the candidate solution so as to obtain a feasible solution with the minimal objective value. To evaluate the performance of the proposed HGA, we randomly generate a total of 2100 instances from seven levels of utilization rate ranged from 0.45 to 0.80. We solve each of those 2100 instances by the proposed HGA and the other solution approaches in the literature. Our experiments show that the proposed HGA outperforms traditional methods for solving the economic lot scheduling problem in flow shops.     

Production scheduling optimisation with machine state and time-dependent energy costs

The increase of energy costs specially in manufacturing system encourages researchers to pay more attention to energy management in different ways. This paper investigates a non-preemptive single-machine manufacturing environment to reduce total energy costs of a production system. For this purpose, two new mathematical models are presented. The first contribution consists of an improvement of a mathematical formulation proposed in the literature which deals and deals with a scheduling problem at machine level to process the jobs in a predetermined order. The second model focuses on the generalisation of the previous one to deal simultaneously with the production scheduling at machine level as well as job level. So, the initial predetermined fixed sequence assumption is removed. Since this problem is NP-hard, an heuristic algorithm and a genetic algorithm based on the second model are developed to provide good solutions in reasonable computational time. Finally, the effectiveness of the proposed models and optimisation methods have been tested with different numerical experiments. In average, for small size instances which the mathematical model provides a solution in reasonable computational time, a gap of 2.2% for the heuristic and 1.82% for GA are achieved comparing to the exact method’s solution. These results demonstrate the accuracy and efficiency of both proposed algorithms.     

A Heuristic Algorithm for the Multi-Item Lot-Sizing Problem with Capacity Constraints

A heuristic algorithm is presented for solving the scheduling of several items in parallel under capacity constraints with setup and carrying costs. The method is based upon finding a lower bound solution for these costs, securing the feasibility of the solution, and improving the feasible solution so obtained until no further improvements can be made. Comparison of the performance of the proposed heuristic algorithm to that of an exact mixed-integer programming model showed that best solution costs found by the heuristic deviated on an average by 1% from the optimal values, while the computing time was on an average 1/140 of that required by the exact method.     

Models and optimisation approaches for scheduling steelmaking–refining–continuous casting production under variable electricity price

This paper studies the steelmaking–refining–continuous casting (SRCC) scheduling problem with considering variable electricity price (SRCCSPVEP). SRCC is one of the critical production processes for steel manufacturing and energy intensive. Combining the technical rules used in iron-steel production practice, time-dependent electricity price is considered to reduce the electricity cost and the associate production cost. A decomposition approach is proposed for the SRCCSPVEP. Without considering the electrical factor, the first phase applies the mathematical programming method to determine the relative schedule plan for each cast. In the second phase, we formulate a scheduling problem of all casts subject to resource constraint and time-dependent electricity price. A heuristic algorithm combined with the constraint propagation is developed to solve this scheduling problem. To investigate and measure the performance of the proposed approach, numerous instances are randomly generated according to the collective data from a well-known iron-steel plant in China. Computational results demonstrate that our algorithm is very efficient and effective in providing high-quality scheduling plans, and the electricity cost can be reduced for the iron-steel plant.     

A genetic algorithm heuristic approach to general outsourcing capacitated production planning problems

This paper addresses a dynamic capacitated production planning (CPP) problem with consideration of outsourcing. Specifically, the outsourcing problem considered in this paper has the following features: (1) all demands are met by production or outsourcing without postponement or backlog, (2) production, inventory, and outsourcing levels all have a limit, and (3) the cost functions are considered arbitrarily and time-varying. These features come together, leading to a so-called general outsourcing CPP problem. In our previous work, an algorithm with pseudo-polynomial time complexity was developed, which includes a formation of a feasible solution region and then a search procedure using dynamic programming techniques. Due to the computational complexity with such an approach, only small and medium problems can be solved in a practical sense. In this paper, we present a genetic algorithm (GA) approach to the same problem. The novelty of this GA approach is that the idea of the feasible solution region is used as a heuristic to guide the searching process. We present a computational experiment to show the effectiveness of the proposed approach.     

A new heuristic for the flowshop scheduling problem to minimize makespan and maximum tardiness

This paper presents a new heuristic for solving the flowshop scheduling problem that aims to minimize makespan and maximize tardiness. The algorithm is able to take into account the aforementioned performance measures, finding a set of non-dominated solutions representing the Pareto front. This method is based on the integration of two different techniques: a multi-criteria decision-making method and a constructive heuristic procedure developed for makespan minimization in flowshop scheduling problems. In particular, the technique for order preference by similarity of ideal solution (TOPSIS) algorithm is integrated with the Nawaz–Enscore–Ham (NEH) heuristic to generate a set of potential scheduling solutions. To assess the proposed heuristic's performance, comparison with the best performing multi-objective genetic local search (MOGLS) algorithm proposed in literature is carried out. The test is executed on a large number of random problems characterized by different numbers of machines and jobs. The results show that the new heuristic frequently exceeds the MOGLS results in terms of both non-dominated solutions, set quality and computational time. In particular, the improvement becomes more and more significant as the number of jobs in the problem increases.     

An optimization-based algorithm for job shop scheduling

Scheduling is a key factor for manufacturing productivity. Effective scheduling can improve on-time delivery, reduce inventory, cut lead times, and improve the utilization of bottleneck resources. Because of the combinatorial nature of scheduling problems, it is often difficult to find optimal schedules, especially within a limited amount of computation time. Production schedules therefore are usually generated by using heuristics in practice. However, it is very difficult to evaluate the quality of these schedules, and the consistency of performance may also be an issue. In this paper, near-optimal solution methodologies for job shop scheduling are examined. The problem is formulated as integer optimization with a “separable” structure. The requirement of on-time delivery and low work-in-process inventory is modelled as a goal to minimize a weighted part tardiness and earliness penalty function. Lagrangian relaxation is used to decompose the problem into individual part subproblems with intuitive appeal. By iteratively solving these subproblems and updating the Lagrangian multipliers at the high level, near-optimal schedules are obtained with a lower bound provided as a byproduct. This paper reviews a few selected methods for solving subproblems and for updating multipliers. Based on the insights obtained, a new algorithm is presented that combines backward dynamic programming for solving low level subproblems and interleaved conjugate gradient method for solving the high level problem. The new method significantly improves algorithm convergence and solution quality. Numerical testing shows that the method is practical for job shop scheduling in industries. This work was supported in part by the National Science Foundation under DMI-9500037, and the Advanced Technology Center for Precision Manufacturing, University of Connecticut.     

Parallel flowshop scheduling using Tabu search

Production scheduling problems in manufacturing systems with parallel machine flowshops are discussed. A mathematical programming model for combined part assignment and job scheduling is developed. The objective of solving the scheduling problem is to minimize a weighted sum of production cost and the cost incurred from late product delivery. The solution of the model is NP-hard. To solve the problem efficiently, a heuristic algorithm combining Tabu search and Johnson's method was proposed. Several numerical examples are presented to illustrate the developed model and the algorithm. Computational results from these example problems are very encouraging.     

Linear Programming Based Genetic Algorithm for the Unequal Area Facility Layout Problem

The facility layout problem (FLP) is generally defined as locating a set of departments in a facility with a given dimension. In this paper, a hybrid genetic algorithm (GA)/linear programming (LP) approach is proposed to solve the FLP on the continuous plane with unequal area departments. This version of the FLP is very difficult to solve optimally due to the large number of binary decision variables in mixed integer programming (MIP) models as well as the lack of tight lower bounds. In this paper, a new encoding scheme, called the location/shape representation, is developed to represent layouts in a GA. This encoding scheme represents relative department positions in the facility based on the centroids and orientations of departments. Once relative department positions are set by the GA, actual department locations and shapes are determined by solving an LP problem. Finally, the output of the LP solution is incorporated into the encoding scheme of the GA. Numerical results are provided for test problems with varying sizes and department shape constraints. The proposed approach is able to either improve on or find the previously best known solutions of several test problems.