Multi-objective short-term production scheduling for open-pit mines: a hierarchical decomposition-based algorithm

This article presents a novel algorithm for solving a short-term open-pit production-scheduling problem in which several objectives, of varying priority, characterize the quality of each solution. A popular approach employs receding horizon control, dividing the horizon into N period-aggregates of increasing size (number of periods or span). An N-period mixed integer program (MIP) is solved for each period in the original horizon to incrementally construct a production schedule one period at a time. This article presents a new algorithm that, in contrast, decomposes the horizon into N period-aggregates of equal size. Given a schedule for these N periods, obtained by solving an N-period MIP, the first of these aggregates is itself decomposed into an N-period scheduling problem with guidance provided on what regions of the mine should be extracted. The performance of this hierarchical decomposition-based approach is compared with that of receding horizon control on a suite of data sets generated from an operating mine producing millions of tons of ore annually. As the number of objectives being optimized increases, the hierarchical decomposition-based algorithm outperforms receding horizon control, in a majority of instances.     

Efficient algorithm to find makespan in manufacturing systems under multiple scheduling perturbations

Manufacturing scheduling improvement heuristics iterate over trial schedules to determine a satisfactory schedule. During each iteration, a performance measure (e.g. makespan) is calculated. The paper presents an efficient algorithm, Structural Perturbation Algorithm (SPA), that accelerates the calculation of the makespan. This means all scheduling improvement heuristics using SPA to calculate makespan for each trial schedule will run faster. To achieve this goal, the manufacturing system is modelled by a Directed Acyclic Graph (DAG). Schedule trials can be described as a perturbed DAG where multiple edges are added and deleted. The major contribution of this research is that SPA can handle multiple edge deletions/additions with a single pass which makes it more efficient in terms of time complexity than current approaches. SPA accomplishes this by partitioning the nodes into three regions based on the locations of the added and deleted edges. Then, SPA updates the length of the affected nodes in each region. The application of SPA is not limited to the scheduling problem. The SPA can be applied in other fields as long as the problem can be described as a Perturbed DAG.     

A scatter search approach to sequence-dependent setup times job shop scheduling

Scheduling jobs on multiple machines is a difficult problem when real-world constraints such as the sequence setup time, setup times for jobs and multiple criteria are used for solution goodness. It is usually sufficient to obtain a near-optimal solution quickly when an optimal solution would require days or weeks of computation. Common scheduling heuristics such as Shortest Processing Time can be used to obtain a feasible schedule quickly, but are not designed for multiple simultaneous objectives. We use a new meta-heuristic known as a scatter search (SS) to solve these types of job shop scheduling problems. The results are compared with solutions obtained by common heuristics, a tabu search, simulated annealing, and a genetic algorithm. We show that by combining the mechanism of diversification and intensification, SS produces excellent results in a very reasonable computation time. The study presents an efficient alternative for companies with a complicated scheduling and production situation.     

A new model for open-pit production and waste-dump scheduling

An open-pit mine schedule defines the optimal sequence of mining valuable (ore) and waste material with the objective of maximizing the value of the project. Given this production schedule, a waste-dump schedule is then developed to determine the optimal waste-rock allocation in waste dumps. Thus, production and waste-dump schedules are managed separately, which leads to an inappropriate consideration of the material haulage cost, suboptimal schedules generating less value, and the incorrect classification of ore and waste. This article proposes a mixed-integer programming-based model that determines the optimal production and waste-rock dumping schedule concurrently with the objective of maximizing the discounted cash flow [net present value (NPV)] of the project. An implementation of the proposed model on a gold-mining operation outperforms the two existing methods [traditional and two-step mixed-integer programming (TSMIP) model] in the context of project NPV as well as its practicality.     

Optimal and heuristic inspection schedules for multistage production systems

Consider a single inspection facility that can be quickly switched among multiple inspection tasks. It can be used (for example) for detecting malfunction (or down state) production stages in a multistage production system. We assume that a properly working (or up state) production stage moves to a down state in any period with fixed probability. The stage then stays down until it is inspected and immediately restored back to an up state. Our purpose is to schedule inspections among the different production stages so as to maximize the fraction of good items produced. An optimal inspection schedule for a two stage production system is provided. For the general case of more than two stages, four heuristics are compared. We conclude that the proposed dynamic schedule is easy to derive, always feasible, and outperforms the static schedules.     

A stochastic multi-item inventory model with unequal replenishment intervals and limited warehouse capacity

Managing inventory levels for multiple products that share warehouse capacity often presents significant coordination challenges. These coordination challenges are further compounded when multiple suppliers use different replenishment schedules for supplying the warehouse. To address these challenges, this paper studies stochastic inventory models for multiple items with both equal and unequal replenishment intervals under limited warehouse capacity. We propose three efficient and intuitively attractive heuristics. We show that these heuristics provide the optimal replenishment quantities in the case of equal replenishment intervals. For the general model, a numerical comparison of the heuristic solutions to the optimal solutions shows that the heuristics yield high quality solutions in very limited time.     

Cyclic scheduling heuristics for a re-entrant job shop manufacturing environment

Two efficient cyclic scheduling heuristics for re-entrant job shop environments were developed. Each heuristic generated an efficient and feasible cyclic production schedule for a job shop in which a single product was produced repetitively on a set of machines was to determine an efficient and feasible cyclic schedule which simultaneously minimized flow time and cycle time. The first heuristic considered a repetitive production re-entrant job shop with a predetermined sequence of operations on a single product with known processing times, set-up and material handling times. The second heuristic was a specialization of the first heuristic where the set-up for an operation could commence even while the preceding operation was in progress. These heuristics have been extensively tested and computational results are provided. Also, extensive analysis of worst-case and trade-offs between cycle time and flow time are provided. The results indicate that the proposed heuristics are robust and yield efficient and superior cyclic schedules with modest computational effort.     

A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem

Scheduling for the flexible job-shop is a very important issue in both fields of combinatorial optimization and production operations. However, due to combination of the routing and sequencing problems, flexible job-shop scheduling problem (FJSP) presents additional difficulty than the classical job-shop scheduling problem and requires more effective algorithms. This paper developed a filtered-beam-search-based heuristic algorithm (named as HFBS) to find sub-optimal schedules within a reasonable computational time for the FJSP with multiple objectives of minimising makespan, the total workload of machines and the workload of the most loaded machine. The proposed algorithm incorporates dispatching rules based heuristics and explores intelligently the search space to avoid useless paths, which makes it possible to improve the search speed. Through computational experiments, the performance of the presented algorithm is evaluated and compared with those of existing literature and those of commonly used dispatching rules, and the results demonstrate that the proposed algorithm is an effective and practical approach for the FJSP.     

Heuristic algorithms for visiting the customers in a rolling schedule environment

In this study, we consider a scheduling problem of a company providing certain kind of services for its customers. In each period, customers call the company to request for the services. In a call j, the customer specifies a date d _j and a time tolerance δ _j . A profit can be realized if the service can be made within the period window d _j ±δ _j . The problem is to construct a schedule for each period so that the average profit of serving a subset of the customer calls is maximized in the long run. We consider the problem in a rolling schedule environment and propose several heuristics based on iterative customer assignment and iterative center-of-gravity scheme for solving it. Extensive computational experiments for problems with various sizes are generated and solved by these heuristics. For the small problem instances, the solutions obtained are compared against the upper bound obtained by solving the LP relaxation of the problem by a column generation scheme. The computational results show that the proposed heuristics all perform very well. For large problem instances, the solutions obtained are compared among the heuristics. The factors affecting the performance of the various heuristics are analyzed and discussed.     

A decision-making approach for nesting scheduling: A textile case

In many industrial cases, the nesting problem and the scheduling problem have to be addressed at the same time. The complexity of the combined problem often prevents to take effectively into account both nesting efficiency and overall production objectives. This paper presents a scheduling approach for the combined problem of production scheduling and nesting. The aim of the proposed approach is to provide a good solution both for the nesting and scheduling problem. The approach involves the generation of scheduling alternatives, their transformation through a rule base mechanism into nesting solutions and finally their evaluation using different criteria that reflect the overall production objectives such as meeting due dates, minimizing of the cost and maximizing the machines and stock sheet utilisation. The proposed approach has been implemented in a software system for the purpose of solving a problem in the textile industry. Specifically, the scheduling of the carpet weaving processa problem of nesting rectangular patterns under complex production constraints-has been examined. A set of experiments has been conducted for producing realistic nesting schedules in order to evaluate the proposed system's performance. The results show that the proposed approach may be applied in real-life manufacturing processes under complex production constraints and multiple objectives.     

Shift scheduling for steppers in the semiconductor wafer fabrication process

In this paper, an approach is proposed for scheduling stepper machines that are acting as bottleneck machines in the semiconductor wafer fabrication process. We consider the problem of scheduling the steppers for an 8 hour shift, determining which types of wafer lots to work on each machine. The scheduling objective is to find the optimal stepper allocations such that the schedule meets target production quantities that have been derived from the given target Work-In-Process (WIP) levels. A Mixed Integer Programming (MIP) model is formulated, and three heuristic approaches are proposed and tested to approximately solve the M1P model. Numerical tests show that one of the proposed heuristics using linear programming relaxation of MIP generates, on average, schedules within 5° of the optimum values.     

Pricing Policies Contingent on Observed Product Quality

Expanded use of incentive contracts has created interest in procurement arrangements in which unit purchase price varies as a function of observed product quality. Under the assumption that at a known cost, a producer can control the true quality of his output, a production and procurement situation is described in which a riskaverse producer and consumer both attempt to maximize expected profit-the consumer by selecting a pricing strategy and sample size, and the producer by then selecting the product quality.

Let product quality be denoted by p. The consumer will desire the selected product quality to be some p*. If at a fixed sample size, n, a price schedule exists which is acceptable to the risk-averse producer and also maximizes producer expected profit at p*, this price schedule is a “motivating” price schedule. For fixed (n, p), a motivating price schedule must be the solution to a specified linear programming problem. It will be a piecewise constant function of the observed quality and need have no more than six distinct price levels.

A method of deriving continuous, piecewise-linear price schedules is briefly described, and extensions of the basic approach are noted.     

An implementation of a decomposition-coordination approach to refinery production scheduling

This paper presents an implementation of a decomposition-coordination approach to petroleum refinery production scheduling. In this approach the scheduling problem is not formulated as a single mathematical programming model to be solved through a computerized system, but it is dealt with as a mathematical programming process, in which a number of small problems are practically solved, and their solutions are combined into an overall schedule Our approach does not pursue an exact optimum, but quite satisfactory schedules have been generated from a practical viewpoint and productivity in the scheduling process has been remarkably raised

An interactive computerized scheduling system has been tailored using a commercial MPS and its Extended Control Language (ECL). The man-hours required for making a final schedule has been reduced to one-third as compared with the previous way     

MATHEMATICAL ANALYSIS OF FACILITY-COMMODITY SCHEDULING PROBLEMS

A number of operational situations exist in which certain facilities are available and where a number of commodities must be processed on some or all of these facilities. The paper describes an algorithm to generate schedules which are near optimal or optimal with respect to the total processing time of all the commodities, the idle lime of facilities and production rate. Thus, these schedules are characterized by near minimal or minimal total processing time and idle time of facilities and near maximal or maximal production rate. Usually this algorithm does not result in the desired schedule after the first application; it is therefore proposed to generate a set “D” of schedules from which the desired schedule can be selected. A decision rule determines the optimal number of elements belonging to set D

In order to justify the concept of the algorithm for the determination of the schedules mentioned above, an analysis is given of the decision tree associated with the sequencing model in terms of the probabilities related to the nodes in the decision tree.     

Heuristics for the N-product,M-stage,economic lot sizing and scheduling problem with dynamic demand

This paper presents a new composite heuristics approach for solving the N-product, M-stage lot sizing and scheduling problem with dynamic demands and limited production capacity. The first phase of these composite heuristics aims at finding a feasible solution. This solution is such that for each period and for each product, the lot size equals the net demand of the considered period plus the demand of a number of upcoming periods. If capacity does not satisfy all demands of a given period, we try to find earlier periods where we can produce the missing units. The second phase is an improvement procedure which recursively attempts to move back each lot, provided that it is both more economical to do so and capacity feasible. We also provide two variants of this heuristic to handle the case where production capacity can be increased by using overtime. Overtime is a usual practice in real life which, in many cases, allows a reduction of the overall cost. The first variant constructs the initial solution without recourse to overtime and introduces overtime only during the solution improvement phase. The second one considers overtime during both the first and second phases. The performance of the proposed heuristics is numerically assessed and the most efficient ones are identified.     

A multi-objective model for multi-project scheduling and multi-skilled staff assignment for IT product development considering competency evolution

We address a multi-skill project scheduling problem for IT product development in this article. The goal is for product development managers to be able to generate an initial schedule at an early stage of development activities. Due to the complexity of the product structure and functionality, an IT product development effort is divided into multiple projects. Each project includes several tasks, and each task must be completed by an employee who has mastered a certain skill to complete it. A pool of multi-skilled employees is available, and the employees’ skill efficiencies are influenced by both learning and forgetting phenomena. Based on the real-world demands of product development managers, three objectives are simultaneously considered: skill efficiency gain, product development cycle time and costs. To solve this problem, we propose a multi-objective non-linear mixed integer programming model. The Non-dominated Sorting Genetic Algorithm II (NSGA-II)is designed to generate an approximation to the optimal Pareto front of this NP-hard multi-objective optimisation problem. The algorithm produces feasible schedules for all the development projects using the serial schedule generation scheme. We adopt penalty values and individual employee adjustments to address resource conflicts and constraint violations. A weighted ideal point method is used to select the final solution from the approximate Pareto solution set. An application case of a new electrical energy saving product implementation in a leading electrical device company in China is used to illustrate the proposed model and algorithm.     

Minimizing earliness–tardiness on a single burn-in oven with a common due date and maximum allowable tardiness constraint

This paper considers a scheduling problem for a single burn-in oven in the semiconductor manufacturing industry where the oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs under the constraint that the maximum tardiness should be less than or equal to the maximum allowable time value. We suggest several two-phase heuristic algorithms for this problem. In the first phase, some heuristic algorithms are developed without maximum allowable tardiness constraint. If the schedule from the first phase violates the maximum tardiness constraint, then the schedule is changed to satisfy maximum allowable tardiness constraint in the second phase. The suggested heuristics are based on genetic algorithms and dominance properties of optimal schedules. We present the results of computational experiments that clearly show the solution quality obtained by the suggested heuristics.     

The single-day surgery scheduling problem: sequential decision-making and threshold-based heuristics

Scheduling elective surgeries is a dynamic, sequential decision-making process that must balance the costs of deferring waiting cases and blocking higher-priority cases. Although other surgery scheduling problems have received extensive treatment in the literature, this paper presents the first single-day scheduling problem formulation to capture this aspect of the scheduling process while also incorporating surgical block schedules, block release policies, and waiting lists. Theoretical results for the special case in which all cases have the same duration motivate a range of threshold-based heuristics for the general problem with multiple case durations. Our computational results demonstrate the effectiveness of the proposed heuristics and show how block release dates affect the quality of the scheduling decisions. Based on these results, we propose a new approach to surgery scheduling. In particular, to make more equitable waiting list decisions, operating room (OR) managers should gradually release unused OR time over the course of several days leading up to the day of surgery.     

A game-theoretic control approach for job shops in the presence of disruptions

A methodology inspired by a game-theoretic view of the on-line control problem for job-shops is developed which allows the use of static off-line schedules in uncertain environments, and the explicit incorporation of deterministic and stochastic information concerning future disturbances. A discrete event dynamic system representation is used to formulate the control problem. The control objectives are to minimize expected makespan and deviations from an off-line schedule. Computational tractability is achieved through a graph-theoretic decomposition of the job-shop scheduling problem, the development of fast rescheduling heuristics, and efficient sampling of future events. A heuristic search algorithm is developed for problem resolution. Experimental results show that the methodology significantly outperforms existing control methods such as ‘total rescheduling’ and ‘right-shift.’ Most importantly, the control methodology demonstrates consistent performance and small CPU time requirements throughout the tests.     

A maintenance driven scheduling cockpit for integrated production and maintenance operation schedule

The production and maintenance functions have objectives that are often in contrast and it is essential for management to ensure that their activities are carried out synergistically, to ensure the maximum efficiency of the production plant as well as the minimization of management costs. The current evolution of ICT technologies and maintenance strategies in the industrial field is making possible a greater integration between production and maintenance. This work addresses this challenge by combining the knowledge of the data collected from physical assets for predictive maintenance management with the possibility of dynamic simulate the future behaviour of the manufacturing system through a digital twin for optimal management of maintenance interventions. The paper, indeed, presents a supporting digital cockpit for production and maintenance integrated scheduling. The tool proposes an innovative approach to manage health data from machines being in any production system and provides support to compare the information about their remaining useful life (RUL) with the respective production schedule. The maintenance driven scheduling cockpit (MDSC) offers, indeed, a supporting decision tool for the maintenance strategy to be implemented that can help production and maintenance managers in the optimal scheduling of preventive maintenance interventions based on RUL estimation. The simulation is performed by varying the production schedule with the maintenance tasks involvement; opportune decisions are taken evaluating the total costs related to the simulated strategy and the impact on the production schedule.The full text can be downloaded at https://link.springer.com/article/10.1007/s40436-021-00380-z