Scheduling the operations of a double-load crane in slab yards

This paper studies a double-load crane scheduling problem (DLCSP) in steel slab yards. A slab yard stores slabs in stacks. To prepare for use in production, some slabs need to be moved from one place to another. These movement tasks are performed by a double-load crane which can hold up to two slabs simultaneously. Given a set of tasks and possibly precedence relationships among them, the scheduling problem is to allocate the tasks to double-load operations and determine the schedule for the crane to perform the tasks so as to minimise the makespan. The problem is first formulated as a mixed integer linear programming (MILP) model with variables representing the order of tasks. Based on properties of the problem, it is then reformulated from a crane operation perspective. Computational experiments are carried out on practical data collected from a steel company. The results show that both models can solve practical sized problems optimally, with the second model being more efficient.     

Mathematical modelling and optimisation of energy-conscious hybrid flow shop scheduling problem with unrelated parallel machines

This paper investigates an energy-conscious hybrid flow shop scheduling problem with unrelated parallel machines (HFSP-UPM) with the energy-saving strategy of turning off and on. We first analyse the energy consumption of HFSP-UPM and formulate five mixed integer linear programming (MILP) models based on two different modelling ideas namely idle time and idle energy. All the models are compared both in size and computational complexities. The results show that MILP models based on different modelling ideas vary dramatically in both size and computational complexities. HFSP-UPM is NP-Hard, thus, an improved genetic algorithm (IGA) is proposed. Specifically, a new energy-conscious decoding method is designed in IGA. To evaluate the proposed IGA, comparative experiments of different-sized instances are conducted. The results demonstrate that the IGA is more effective than the genetic algorithm (GA), simulating annealing algorithm (SA) and migrating birds optimisation algorithm (MBO). Compared with the best MILP model, the IGA can get the solution that is close to an optimal solution with the gap of no more than 2.17% for small-scale instances. For large-scale instances, the IGA can get a better solution than the best MILP model within no more than 10% of the running time of the best MILP model.     

A mixed integer goal programming model for discrete values of design requirements in QFD

A main feature of quality function deployment (QFD) planning process is to determine target values for the design requirements (DRs) of a product, with a view to achieving a higher level of overall customer satisfaction. However, in real world applications, values of DRs are often discrete instead of continuous. Therefore, a mixed integer linear programming (MILP) model considering discrete data is suggested. As opposed to the existing literature, the fulfilment levels of DRs are assumed to have a piece-wise linear relationship with cost; because, constraints of technology and resource rarely provides a linear relationship in manufacturing systems. In the proposed MILP model, we considered customer satisfaction as the only goal. But, QFD process may be necessary to optimise cost and technical difficulty goals as well as customer satisfaction. Therefore, by developing the MILP model with multi-objective decision making (MODM) approach, a novel mixed integer goal programming (MIGP) model is proposed to optimise these goals simultaneously. Finally, MILP model solution turns out to be a more realistic approach to real applications because piece-wise linear relationship is taken into account. The solution of MIGP model provided different alternative results to decision makers according to usage of the lexicographic goal programming (LGP) approach. The applicability of the proposed models in practice is demonstrated with a washing machine development problem.     

A nested column generation algorithm to the meta slab allocation problem in the steel making industry

This paper addresses one of the key operational decision problems in the steel industry which is related to the allocation of orders to stock materials in the surplus inventory. The meta slab allocation problem can be stated as the ‘multi-stage multiple knapsack problem’ where the problem is to design slabs using orders with similar properties (the first stage) and allocating these designed slabs into the existing meta slabs in the inventory yard (the second stage). The objective of the problem is to maximise the allocated order weights in slabs and meta slabs. For the given problem, we propose a column generation algorithm, where a column in the master problem represents meta slabs and the sub problem is to design ‘bins’, here slabs with the given orders. The sub problem itself also becomes a multiple knapsack problem and we proposed a practical set-partitioning heuristic. The proposed algorithm was tested with daily operation data given from an integrated steel company in the Asia Pacific. The computational results showed that the proposed heuristic solved the real instances pretty well. The proposed algorithm was successfully deployed to the integrated steel mill.     

Multi-item production routing problem with backordering: a MILP approach

The aim of this paper is to present mixed integer linear programming formulations for the production routing problem with backordering (PRP-B) and a new hybrid heuristic to solve the problem. The PRP-B is considered in the context of a supply chain consisting of a production facility with limited production and storage capacities and geographically dispersed points of sale with limited storage capacities. The PRP-B integrates multiple item lot sizing decisions and vehicle routing decisions to the points of sale, where backordering of end customer demands is allowed at a penalty. Two integrated mixed integer programming models are formulated and a solution procedure consisting of a relax-and-fix heuristic combined with a local search algorithm is proposed. The numerical results show that this hybrid heuristic outperforms a state-of-the-art MIP commercial solver, in terms of solution quality and CPU times.     

A heuristic-based approach to integrate the product line selection decision to the supply chain configuration

Product platform development (PPD) as an approach to mass customisation (MC) helps an organisation to reduce costs as well as ensure timely deliveries. Varieties are offered to different market segments by combining and incorporating different modules at different levels. Modules at different levels are essentially features that a customer segment is looking for. It is apparent that overall optimisation would require simultaneous consideration of not only PPD but also other supply chain constraints. In this paper, an attempt has been made to develop a mixed integer linear programming (MILP) model for sourcing, production planning, and PPD decisions. Based on analyses of the model, a heuristic solution procedure has been suggested. The heuristic developed in this paper attempts to decompose the problem and then assimilate the outputs from the simpler parts to obtain the final solution. Finally, a simple example to illustrate the solution procedure is presented.     

An optimisation model and its effective beam search heuristics for floor-storage warehousing systems

This paper presents an optimisation model and its effective solution technique using beam search heuristic for floor-storage warehousing systems. For a floor-storage system, storage can be accessed from the top of stacks only. The objective is to minimise the number of re-handling operations by optimally determining the storage location and by grouping products for each customer that fit a given sequence for receiving and retrieving operations. An integer programming model is formulated and an approximate solution technique based on the beam search method is proposed to solve the problem by incorporating effective heuristics to reduce the search space using future receiving and retrieving requests. The effectiveness of the proposed method is demonstrated for industrial warehousing problems in a steel plant with 58 storage areas involving more than 3000 retrieving operations. The proposed solution method is shown to be more efficient than the traditional branch-and-bound method for solving integer programming problems.     

A strategic decision support system for logistics and supply chain network design

This paper aims to develop a strategic decision support system for logistics and supply chain network design of a multi-stage, multi-commodity, and multi-period distribution and transportation system. A mixed integer linear programming model is proposed to tackle the problem while minimizing the operating, transportation and handling cost through all tiers of the supply chain network. A genetic algorithm based method has been proposed to solve the problem in a large scale realistic environment. The efficacy of the developed strategic decision support model in achieving better utilization of network and resources to fulfil the customer demand is demonstrated using illustrative scenarios inspired from the real case of a logistics company.     

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.     

A tabu search algorithm for simultaneous machine/AGV scheduling problem

Machines and automated guided vehicles (AGVs) scheduling problems are two essential issues that need to be addressed for the efficiency of the overall production system. The purpose of this paper is to study the simultaneous scheduling problem of machines and AGVs in a flexible manufacturing system (FMS) since the global optimum cannot be reached by considering each of them individually. In this paper, a mixed integer linear programming (MILP) model is developed with the objective of makespan minimisation. The MILP model consists of the following two constraint sets: machines and AGVs scheduling sub-problems. As both sub-problems are known to be NP-hard, a heuristic algorithm based on tabu search (TS) is proposed to get optimal or near to optimal solution for large-size problems within reasonable computation time. The proposed algorithm includes a novel two-dimensional solution representation and the generation of two neighbour solutions, which are alternately and iteratively applied to improve solutions. Moreover, an improved lower bound calculation method is introduced for the large-size problems. Computational results show the superior performance of the TS algorithm for the simultaneous scheduling problem.     

Scheduling commercial advertisements for television

The problem of scheduling the commercial advertisements in the television industry is investigated. Each advertiser client demands that the multiple airings of the same brand advertisement should be as spaced as possible over a given time period. Moreover, audience rating requests have to be taken into account in the scheduling. This is the first time this hard decision problem is dealt with in the literature. We design two mixed integer linear programming (MILP) models. Two constructive heuristics, local search procedures and simulated annealing (SA) approaches are also proposed. Extensive computational experiments, using several instances of various sizes, are performed. The results show that the proposed MILP model which represents the problem as a network flow obtains a larger number of optimal solutions and the best non-exact procedure is one that uses SA.     

A multi-objective optimisation model to integrating flexible process planning and scheduling based on hybrid multi-objective simulated annealing

Process planning and production scheduling play important roles in manufacturing systems. In this paper we present a mixed integer linear programming (MILP) scheduling model, that is to say a slot-based multi-objective multi-product, that readily accounts for sequence-dependent preparation times (transition and set up times or machine changeover time). The proposed scheduling model becomes computationally expensive to solve for long time horizons. The aim is to find a set of high-quality trade-off solutions. This is a combinatorial optimisation problem with substantially large solution space, suggesting that it is highly difficult to find the best solutions with the exact search method. To account for this, the hybrid multi-objective simulated annealing algorithm (MOHSA) is proposed by fully utilising the capability of the exploration search and fast convergence. Two numerical experiments have been performed to demonstrate the effectiveness and robustness of the proposed algorithm.     

Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups

This study considers selective disassembly sequencing under the sequential disassembly environment in which one component is obtained at each disassembly operation. The problem is to determine the sequence of disassembly operations to obtain multiple target components of a used or end-of-life product for the purpose of repair, reuse, remanufacturing, disposal, etc. In particular, we consider sequence-dependent setups in which setup costs depend on the disassembly operation just completed and on the operation to be processed. The problem is represented as a disassembly precedence graph and then a new integer programming model is suggested for the objective of minimising the total disassembly cost. After it is proved that the problem is NP-hard, we suggest two types of heuristics: (1) branch and fathoming algorithm for small-to-medium-sized instances; and (2) priority-rule-based algorithm for large-sized instances. A series of computational experiments, i.e., effectiveness of the new integer programming model and performances of the two heuristic types, were done on various test instances, and the results are reported. In addition, to show the applicability of the mathematical model and the solution algorithms, a case study is reported on an end-of-life electronic calculator.     

A simple and robust Monte Carlo hybrid local search algorithm for the facility location problem

In this article, a new Monte Carlo hybrid local search algorithm (Hyb-LS) is proposed for solving the uncapacitated facility location problem. Hyb-LS is based on repeated sampling using two local search strategies based on best improvement and randomized neighbourhood search. A major advantage of Hyb-LS for its practical use is that the number of restarts is its only parameter to tune. The algorithm is also simple to reimplement, scalable and robust to changes in coefficients within a problem instance. The stopping criterion for local search is learned automatically. Experimental results are presented for four representative and contrasting cost and distance models. The results obtained by Hyb-LS are compared to the optimal or near-optimal solutions found by a mixed integer linear programming (MILP) solver with a generous time limit. For three out of the four models, Hyb-LS obtains better solutions than the upper bound found by the MILP solver for at least one instance.     

Harmony search optimization algorithm for a novel transportation problem in a consolidation network

This article presents a new harmony search optimization algorithm to solve a novel integer programming model developed for a consolidation network. In this network, a set of vehicles is used to transport goods from suppliers to their corresponding customers via two transportation systems: direct shipment and milk run logistics. The objective of this problem is to minimize the total shipping cost in the network, so it tries to reduce the number of required vehicles using an efficient vehicle routing strategy in the solution approach. Solving several numerical examples confirms that the proposed solution approach based on the harmony search algorithm performs much better than CPLEX in reducing both the shipping cost in the network and computational time requirement, especially for realistic size problem instances.     

考虑班种约束的呼叫中心排班优化模型与算法

一些呼叫中心设置早班、晚班和两段班班种;排班时规定员工周内同班种的班次当班,并且限制两段班当班员工占比。构建该实际情景的坐席人员排班问题整数规划模型。鉴于问题难解性,首先通过问题结构层次分解,以及对班种与班次覆盖区段人力需求量化指标的表征刻画,提出启发式算法生成解方案;然后采用基于模拟退火机制的邻域搜索算法改善解方案。计算实验表明整数规划模型适于求解小规模排班问题最优解,而上述两阶段优化算法能够获得大规模问题优化解。研究表明,在优化人力成本情况下可兼顾坐席人员工作时间高规律性。     

A bilinear programming model and a modified branch-and-bound algorithm for production planning in steel rolling mills with substitutable demand

In this paper, we address an instance of the dynamic capacitated multi-item lot-sizing problem (CMILSP) typically encountered in steel rolling mills. Production planning is carried out at the master production schedule level, where the various end items lot sizes are determined such that the total cost is minimised. Through incorporating the various technological constraints associated with the manufacturing process, the integrated production–inventory problem is formulated as a mixed integer bilinear program (MIBLP). Typically, such class of mathematical models is solved via linearisation techniques which transform the model to an equivalent MILP (mixed integer linear program) at the expense of increased model dimensionality. This paper presents an alternative branch-and-bound based algorithm that exploits the special structure of the mathematical model to minimise the number of branches and obtain the bound at each node. The performance of our algorithm is benchmarked against that of a classical linearisation technique for several problem instances and the obtained results are reported.     

Pattern-set generation algorithm for the one-dimensional multiple stock sizes cutting stock problem

A pattern-set generation algorithm (PSG) for the one-dimensional multiple stock sizes cutting stock problem (1DMSSCSP) is presented. The solution process contains two stages. In the first stage, the PSG solves the residual problems repeatedly to generate the patterns in the pattern set, where each residual problem is solved by the column-generation approach, and each pattern is generated by solving a single large object placement problem. In the second stage, the integer linear programming model of the 1DMSSCSP is solved using a commercial solver, where only the patterns in the pattern set are considered. The computational results of benchmark instances indicate that the PSG outperforms existing heuristic algorithms and rivals the exact algorithm in solution quality.     

A hybrid flowshop scheduling problem for a cold treating process in seamless steel tube production

Seamless steel tubes often have various categories and specifications, which further require complicated operations in production, especially in the cold treating process (CTP). This paper investigates the scheduling problem using the seamless tube plant of Baoshan Iron and Steel Complex as a study background. By considering the practical production constraints such as sequence-dependent setup times, maintenance schedule, intermediate material buffers, job-machine matches, we formulate the hybrid flowshop scheduling problem with a non-linear mixed integer programming model (NMIP). In addition, our model provides a flexibility to remove the permutation assumption, which is often a limitation in early studies. In order to obtain the solution of the above NMIP problem, a two-stage heuristic algorithm is proposed and it combines a modified genetic algorithm and a local search method. With real production instances, our computation experiments indicate that the proposed algorithm is efficient and it outperforms several other approaches. Industrial implementation also shows that such a scheduling tool brings a cost saving of more than 10% and it substantially reduces the computation time. Our study also illustrates the need of relaxing permutation assumption in such a scheduling problem with complicated operation sequences.     

Minimising interference for scheduling two parallel machines with a single server

In this paper, we consider the problem of scheduling a set of jobs on two parallel machines with set-up times. The set-up has to be performed by a single server. The objective is to minimise the forced idle time. The problem of minimising the forced idle time (interference problem) is known to be unary NP-hard for the case of two machines and equal set-up and arbitrary processing times. We propose a mixed integer linear programming model, which describes a special class of schedules where the jobs from a list are scheduled alternatively on the machines, and a heuristic algorithm is tested on instances with up to 100,000 jobs. The computational results indicate that the algorithm has an excellent performance even for very large instances, where mostly an optimal solution is obtained within a very small computational time.