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.     

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.     

Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling

Factory management plays an important role in improving the productivity and quality of service in the production process. In particular, the distributed permutation flow shop scheduling problem with multiple factories is considered a priority factor in the factory automation. This study proposes a novel model of the developed distributed scheduling by supplementing the reentrant characteristic into the model of distributed reentrant permutation flow shop (DRPFS) scheduling. This problem is described as a given set of jobs with a number of reentrant layers is processed in the factories, which compromises a set of machines, with the same properties. The aim of the study is to determine the number of factory needs to be used, jobs assignment to certain factory and sequence of job assigned to the factory in order to simultaneously satisfy three objectives of minimizing makespan, total cost and average tardiness. To do this, a novel multi-objective adaptive large neighborhood search (MOALNS) algorithm is developed for finding the near optimal solutions based on the Pareto front. Various destroy and repair operators are presented to balance between intensification and diversification of searching process. The numerical examples of computational experiments are carried out to validate the proposed model. The analytical results on the performance of proposed algorithm are checked and compared with the existing methods to validate the effectiveness and robustness of the proposed potential algorithm in handling the DRPFS problem.     

An energy-efficient scheduling scheme for time-constrained tasks in local mobile clouds

Mobile Cloud Computing (MCC) enables mobile devices to use resource providers other than mobile devices themselves to host the execution of mobile applications. Various mobile cloud architectures and scheduling algorithms have been studied recently. However, how to utilize MCC to enable mobile devices to run complex real-time applications while keeping high energy efficiency remains a challenge. In this paper, firstly, we introduce the local mobile clouds formed by nearby mobile devices and give the mathematical models of the mobile devices and their applications. Secondly, we formulate the scheduling problem in local mobile clouds. After describing the resource discovery scheme and the adaptive, probabilistic scheduling algorithm, we finally validate the performance of the proposed algorithm by simulation experiments.