Automatic design for shop scheduling strategies based on hyper-heuristics: A systematic review

Against the background of smart manufacturing and Industry 4.0, how to achieve real-time scheduling has become a problem to be solved. In this regard, automatic design for shop scheduling based on hyper-heuristics has been widely studied, and a number of reviews and scheduling algorithms have been presented. Few studies, however, have specifically discussed the technical points involved in algorithm development. This study, therefore, constructs a general framework for automatic design for shop scheduling strategies based on hyper-heuristics, and various state-of-the-art technical points in the development process are summarized. First, we summarize the existing types of shop scheduling strategies and classify them using a new classification method. Second, we summarize an automatic design algorithm for shop scheduling. Then, we investigate surrogate-assisted methods that are popular in the current algorithm field. Finally, current problems and challenges are discussed, and potential directions for future research are proposed.     

Earliness–tardiness minimization on scheduling a batch processing machine with non-identical job sizes

This paper considers the scheduling problem of minimizing earliness–tardiness (E/T) on a single batch processing machine with a common due date. The problem is extended to the environment of non-identical job sizes. First, a mathematical model is formulated, which is tested effectively under IBM ILOG CPLEX using the constraint programming solver. Then several optimal properties are given to schedule batches effectively, and by introducing the concept of ARB (Attribute Ratio of Batch), it is proven that the ARB of each batch should be made as small as possible in order to minimize the objective, designed as the heuristic information for assigning jobs into batches. Based on these properties, a heuristic algorithm MARB (Minimum Attribute Ratio of Batch) for batch forming is proposed, and a hybrid genetic algorithm is developed for the problem under study by combining GA (genetic algorithm) with MARB. Experimental results demonstrate that the proposed algorithm outperforms other algorithms in the literature, both for small and large problem instances.     

A bi-layer optimization approach for a hybrid flow shop scheduling problem involving controllable processing times in the steelmaking industry

A steelmaking-continuous casting (SCC) scheduling problem is an example of complex hybrid flow shop scheduling problem (HFSSP) with a strong industrial background. This paper investigates the SCC scheduling problem that involves controllable processing times (CPT) with multiple objectives concerning the total waiting time, earliness/tardiness and adjusting cost. The SCC scheduling problem with CPT is seldom discussed in the existing literature. This study is motivated by the practical situation of a large integrated steel company in which the just-in-time (JIT) and cost-cutting production strategy have become a significant concern. To address this complex HFSSP, the scheduling problem is decomposed into two subproblems: a parallel machine scheduling problem (PMSP) in the last stage and an HFSSP in the upstream stages. First, a hybrid differential evolution (HDE) algorithm combined with a variable neighborhood decomposition search (VNDS) is proposed for the former subproblem. Second, an iterative backward list scheduling (IBLS) algorithm is presented to solve the latter subproblem. The effectiveness of this bi-layer optimization approach is verified by computational experiments on well-designed and real-world scheduling instances. This study provides a new perspective on modeling and solving practical SCC scheduling problems.     

A mathematical model for open pit mine production scheduling with Grade Engineering® and stockpiling

This paper presents the development and implementation of an innovative mixed integer programming based mathematical model for an open pit mining operation with Grade Engineering framework. Grade Engineering comprises a range of coarse-separation based pre-processing techniques that separate the desirable (i.e. high-grade) and undesirable (i.e. low-grade or uneconomic) materials and ensure the delivery of only selected quantity of high quality (or high-grade) material to energy, water, and cost-intensive processing plant. The model maximizes the net present value under a range of operational and processing constraints. Given that the proposed model is computationally complex, the authors employ a data pre-processing procedure and then evaluate the performance of the model at several practical instances using computation time, optimality gap, and the net present value as valid measures. In addition, a comparison of the proposed and traditional (without Grade Engineering) models reflects that the proposed model outperforms the traditional formulation.     

Two-agent two-machine flowshop scheduling with learning effects to minimize the total completion time

We study a two-agent scheduling problem in a two-machine permutation flowshop with learning effects. The objective is to minimize the total completion time of the jobs from one agent, given that the maximum tardiness of the jobs from the other agent cannot exceed a bound. We provide a branch-and-bound algorithm for the problem. In addition, we present several genetic algorithms to obtain near-optimal solutions. Computational results indicate that the algorithms perform well in either solving the problem or efficiently generating near-optimal solutions.     

Joint scheduling and power control supporting multicasting in wireless ad hoc networks

This paper addresses the problem of power control in a multihop wireless network supporting multicast traffic. We face the problem of forwarding packet traffic to multicast group members while meeting constraints on the signal-to-interference-plus-noise ratio (SINR) at the intended receivers. First, we present a distributed algorithm which, given the set of multicast senders and their corresponding receivers, provides an optimal solution when it exists, which minimizes the total transmit power. When no optimal solution can be found for the given set of multicast senders and receivers, we introduce a distributed, joint scheduling and power control algorithm which eliminates the weak connections and tries to maximize the number of successful multicast transmissions. The algorithm allows the other senders to solve the power control problem and minimize the total transmit power. We show that our distributed algorithm converges to the optimal solution when it exists, and performs close to centralized, heuristic algorithms that have been proposed to address the joint scheduling and power control problem.     

Scheduling railway traffic at a construction site

We consider the problem of rescheduling trains in the case where one track of a railway section consisting of two tracks in opposing directions is closed due to construction activities. After presenting an appropriate model for this situation we derive a polynomial algorithm for the subproblem of finding an optimal schedule with minimal latenesss if the subsequences of trains for both directions outside the construction site are fixed. Based on this algorithm we propose a local search procedure for the general problem of finding good schedules and report test results for some real world instances. Received: December 8, 1999 / Accepted: May 2, 2001     

Control of discrete time nonlinear systems with a time-varying structure

In this paper, we present a control methodology for a class of discrete time nonlinear systems that depend on a possibly exogenous scheduling variable. This class of systems consists of an interpolation of nonlinear dynamic equations in strict feedback form, and it may represent systems with a time-varying nonlinear structure. Moreover, this class of systems is able to represent some cases of gain scheduling control, Takagi-Sugeno fuzzy systems, as well as input-output realizations of nonlinear systems which are approximated via localized linearizations. We present two control theorems, one using what we call a “global” approach (akin to traditional backstepping), and a “local” approach, our main result, where backstepping is again used but the control law is an interpolation of local control terms. An aircraft wing rock regulation problem with varying angle of attack is used to illustrate and compare the two approaches.     

Contractor Prebid Planning Principles

Planning is an essential function of project management. Yet, many small- and medium-sized contractors do a relatively poor job of operational planning. Better prebid plans will reduce costs, shorten schedules, and improve labor productivity. Unfortunately, the published literature offers little guidance for smaller contractors on what constitutes effective planning. Most papers describe planning as a macrolevel process for owners. Most emphasize scope definition for industrial projects. This paper describes a microlevel planning process for contractors. It consists of eight steps which are: (1) assess contract risks; (2) develop a preliminary execution plan; (3) develop site layout plans; (4) identify the sequences that are essential-to-success; (5) develop detailed operational plans; (6) develop proactive strategies to assure construction input into design; (7) revise the preliminary plan; and (8) communicate and enforce the plan. The entire process is illustrated with a case study project and is fully illustrated with figures which show how to integrate the work of multiple contractors, keep key resources (crews or equipment) fully engaged with no downtime, provide time buffers so the work of follow on crews can be efficiently done, expedite the schedule using multiple work stations and concurrent work, ways to communicate the work plan to the superintendent and foremen, and how to assess the feasibility of various work methods. The steps are easy to understand and implement. They will yield immediate positive results.