A comparison of five hybrid metaheuristic algorithms for unrelated parallel-machine scheduling and inbound trucks sequencing in multi-door cross docking systems

The objective of this paper is to develop five hybrid metaheuristic algorithms, including three hybrid ant colony optimization (hACO) variants, and compare their performances in two related applications: unrelated parallel machine scheduling and inbound truck sequencing in a multi-door cross docking system in consideration of sequence dependent setup, and both zero and nonzero release time. The three hACO variants were modified and adapted from the existing literature and they differ mainly in how a solution is coded and decoded, how a pheromone matrix is represented, and the local search methods employed. The other two hybrids are newly constructed hybrid simulated annealing (hSA) algorithms, which are built based on the authors’ knowledge and experience. The evaluation criteria are computational time and the objective function value, i.e., makespan. Based on the results of computational experiments the simulated annealing-tabu search hybrid turns out to be the best if maximal CPU time is used as the stopping criterion and the 2-stage hACO variant is the best if maximal number of evaluations is the stopping criterion. The contributions of this paper are: (i) being the first to carry out a comparative study of hybrid metaheuristics for the two selected applications, (ii) being the first to consider nonzero truck arrival time in multi-door cross docking operations, (iii) identifying which hACO variant is the best among the three, and (iv) investigating the effect of release time on the makespan.     

An effective heuristic for adaptive control of job sequences subject to variation in processing times

Variation in sequential task processing times is common in manufacturing systems. This type of disturbance challenges most scheduling methods since they cannot fundamentally change job sequences to adaptively control production performance as jobs enter the system because actual processing times, are not known in advance. Some research literature indicates that simple rules are more suitable than algorithmic scheduling methods for adaptive control. In this work, a ‘state space – average processing time’ (SS-APT) heuristic is proposed and compared to four most commonly used scheduling rules and two well-established heuristics based on Taillard’s benchmarks. It is shown that the adaptive control is made possible under variation in processing times given the flexibility and strong performance of the SS-APT heuristic, especially for work-in-process inventory control.     

Discrete-time mixed-integer programming models and solution methods for production scheduling in multistage facilities

We address the problem of production scheduling in multi-product multi-stage batch plants. Unlike most of the previous works, which propose continuous-time models, we study discrete-time mixed-integer programming models and solution methods. Specifically, we discuss two models based on network representations of the facility and develop two new models inspired by the Resource-Constrained Project Scheduling Problem. Furthermore, we propose different solution methods, including tightening methods based on processing unit availability, a reformulation based on processing unit occupancy, and an algorithm to refine approximate solutions for large-scale instances. Finally, we present a comprehensive computational study which shows that speedups of up to four orders of magnitude in are observed when our models and methods are compared to existing approaches.     

A new scheduling technique for the resource–constrained project scheduling problem with discounted cash flows

In this paper, we discuss the resource–constrained project scheduling problem with discounted cash flows. We introduce a new schedule construction technique which moves sets of activities to improve the project net present value and consists of two steps. In particular, the inclusion of individual activities into sets, which are then moved together, is crucial in both steps. The first step groups the activities based on the predecessors and successors in the project network, and adds these activities to a set based on their finish time and cash flow. The second step on the contrary does so based on the neighbouring activities in the schedule, which may but need not include precedence related activities. The proposed scheduling method is implemented in a genetic algorithm metaheuristic and we employ a penalty function to improve the algorithm’s feasibility with respect to a tight deadline. All steps of the proposed solution methodology are tested in detail and an extensive computational experiment shows that our results are competitive with existing work.     

A branch and bound algorithm for scheduling problem of a robot‐centered manufacturing cell

Abstract

An alternative formulation of the scheduling problem in a robot‐centered manufacturing cell has been described here, which was originally formulated by Lin et al. [7] as a mixed integer programming problem. An efficient procedure based on the branch and bound technique has been proposed. In order to reduce the complexity of the branching procedure, several sequencing rules [4] have been imbedded into the proposed procedure and an integrated algorithm has then been presented. The computational results have indicated the proposed algorithm to be efficient. Finally, conclusions and some suggestions are given.     

A desired load distribution model for scheduling of unrelated parallel machines

Scheduling problems concern the allocation of limited resources over time among both parallel and sequential activities. Load balancing has been adopted as an optimization criterion for several scheduling problems. However, in many practical situations, a load-balanced solution may not be feasible or attainable. To deal with this limitation, this paper presents a generic mathematical model of load distribution for resource allocation, called desired load distribution (DLD). The objective is to develop a DLD model for scheduling of unrelated parallel machines that can be used both in centralized resource management settings and in agent-based distributed scheduling systems. The paper describes the proposed DLD model in details, presents a dynamic programming based optimization algorithm for the proposed model, and then discusses its application to agent-based distributed scheduling.     

Anticipation and flexibility in dynamic scheduling

Many real-world optimization problems change over time and require frequent re-optimization. We suggest that in such environments, an optimization algorithm should reflect the problem's dynamics and explicitly take into account that changes to the current solution are to be expected. We claim that this can be achieved by having the optimization algorithm search for solutions that are not only good, but also flexible, i.e. easily adjustable if necessary in the case of problem changes. For the example of a job-shop with jobs arriving non-deterministically over time, we demonstrate that avoiding early idle times increases flexibility, and thus that the incorporation of an early idle time penalty as secondary objective into the scheduling algorithm can greatly enhance the overall system performance.     

Fuzzy uncertainty modelling for project planning: application to helicopter maintenance

Maintenance is an activity of growing interest, especially for critical systems. In particular, aircraft maintenance costs are becoming an important issue in the aeronautical industry. Managing an aircraft maintenance centre is a complex activity. One of the difficulties comes from the numerous uncertainties that affect the activity and disturb the plans in the short and medium term. Based on a helicopter maintenance planning and scheduling problem, we study in this paper the integration of uncertainties into tactical and operational multi-resource, multi-project planning (respectively Rough Cut Capacity Planning and the Resource Constraint Project Scheduling Problem). Our main contributions are in modelling the periodic workload on a tactical level considering uncertainties in macro-task work content, and modelling the continuous workload on the operational level considering uncertainties in task duration. We model uncertainties using a fuzzy/possibilistic approach instead of a stochastic approach since very limited data are available. We refer to the problems as the Fuzzy Rough Cut Capacity Problem (FRCCP) and the Fuzzy Resource Constraint Project Scheduling Problem (RCPSP). We apply our models to helicopter maintenance activity within the frame of the Helimaintenance project, an industrial project approved by the French Aerospace Valley cluster that aims at building a centre for civil helicopter maintenance.     

Scheduling of open-pit phosphate mine extraction

Open-pit deposits are often characterised by a stack of layers of different geological nature. Some layers are worthless while the ore of the others is of a varying economic value depending on grade. To reach a layer, it is necessary to have first removed the upper layers above the extraction zone. This action results in uncovering the layer in this particular place and in facilitating access to the layers below. This extraction process involves a series of 2–7 basic operations; each one is performed by a machine, some of which are able to perform up to three different operations. Ensuring the consistency of mining extraction scheduling over a few months, in order to meet known or forecast demand, is a challenging task. A mining extraction model based on mathematical programming is proposed but it is hardly usable, due to its size. Therefore, a model based on a Discrete Event Simulation, is created to test how ore supplies are affected by the tactical and operational decisions relating to the choice of parcels to be processed and to the allocation of machines to the different basic operations.     

Day of the week lost time occupational injury trends in the US by gender and industry and their implications for work scheduling

While there is a growing body of research on the impact of work schedules on the risk of occupational injuries, there has been little investigation into the impact that the day of the week might have. The present research was completed to explore day of the week trends, reasons for such trends and the corresponding implications for work scheduling. Data for the number of injuries and illnesses involving days away from work (lost time; LT) in 2004 were provided by the US Bureau of Labor Statistics Office of Safety and Health Statistics. Data from the American Time Use Survey database were used to estimate work hours in 2004. From these two data sources, the rate of LT injuries and illnesses (per 200 000 work hours) by day of the week, industry sector and gender were estimated. The analysis revealed clear differences by day of the week, gender and major industry sector. Sundays had the highest rate overall – nearly 37% higher than the average of the remaining days, Monday to Saturday. Mondays had the next highest rate followed closely by Saturdays. This pattern was not the same for males and females. For males, Mondays had the highest LT rate (27% higher than the average of all other days) with all remaining days having essentially the same rate. For females, Sundays and Saturdays had much higher LT rates – 122% and 60% higher, respectively, than the average weekday rate. There were also differences by industry and differences between genders by industry. The present analysis suggests that several factors may be contributing to the weekend and Monday trends observed. Lower-tenured (and younger) workers on the weekends, lower female management/supervision and second jobs on the weekend seem to be contributors to the high Saturday and Sunday LT rates. Differences in day of the week employment by industry did not account for the trends observed. Fraud and overtime also could not be confirmed as contributing to these trends. Monday trends were more complex to explain, with possible explanations including non-work-related weekend injuries being reported on Mondays, soft-tissue symptoms becoming more noticeable on Mondays, greater Monday morning flexion risk and reduced supervision in the construction industry on Mondays. Interpretation of these trends and the implications for work scheduling are discussed.