Assessing the resource usage in scheduling with incompatibilities

In the field of resource constrained scheduling, the papers in the literature are mainly focused on minimizing the maximum completion time of a set of tasks to be carried out, paying attention to respecting the maximum simultaneous availability of each resource type in the system. This work, instead, considers the issues of balancing the resource usage and minimizing the peak of the resources allocated each time in the schedule, while keeping the makespan low. To this aim we propose a local search algorithm which acts as a multi start greedy heuristic. Extensive experiments on various randomly generated test instances are provided. Furthermore, we present a comparison with lower bounds and known heuristics. Correspondence to: Massimiliano CaramiaWe wish to thank the anonymous referees for their useful comments which have led to this improved version of the paper.     

Scheduling Multi-Mode Resource-Constrained Projects Using Heuristic Rules Under Uncertainty Environment

Project scheduling is a key objective of many models and is the proposed method for project planning and management. Project scheduling problems depend on precedence relationships and resource constraints, in addition to some other limitations for achieving a subset of goals. Project scheduling problems are dependent on many limitations, including limitations of precedence relationships, resource constraints, and some other limitations for achieving a subset of goals. Deterministic project scheduling models consider all information about the scheduling problem such as activity durations and precedence relationships information resources available and required, which are known and stable during the implementation process. The concept of deterministic project scheduling conflicts with real situations, in which in many cases, some data on the activity' s durations of the project and the degree of availability of resources change or may have different modes and strategies during the process of project implementation for dealing with multi-mode conditions surrounded by projects and their activity durations. Scheduling the multi-mode resource-constrained project problem is an optimization problem whose minimum project duration subject to the availability of resources is of particular interest to us. We use the multi-mode resource allocation and scheduling model that takes into account the dynamicity features of all parameters, that is, the scheduling process must be flexible to dynamic environment features. In this paper, we propose five priority heuristic rules for scheduling multi-mode resource-constrained projects under dynamicity features for more realistic situations, in which we apply the proposed heuristic rules (PHR) for scheduling multi-mode resource-constrained projects. Five projects are considered test problems for the PHR. The obtained results rendered by these priority rules for the test problems are compared by the results obtained from 10 well-known heuristics rules rendered for the same test problems. The results in many cases of the proposed priority rules are very promising, where they achieve better scheduling dates in many test case problems and the same results for the others. The proposed model is based on the dynamic features for project topography.     

Route-reduction-based dynamic programming for large-scale satellite range scheduling problem

Satellites offer many services through communication with stations, such as tracking, navigation, telecommand uplink, earth observation, etc. How to coordinate these services is referred to as the satellite range scheduling problem (SRSP). In the research, it is found that only the resources (referring to time slots of stations) requested by more than one satellite simultaneously influence scheduling results. These resources are called critical resources and selected as scheduling elements, which makes some jobs optimally served in advance and the problem be decomposable into a multi-stage decision process, so dynamic programming is suitable to be employed. For large-scale SRSPs, a route-reduction-based dynamic programming (RR-DP) is presented, wherein a multi-level route reduction strategy is adopted to alleviate ‘the curse of dimensionality’. Experimental results reveal that RR-DP can find optimal solutions for small-to-medium sized problems and outperforms state-of-the-art methods for large-scale problems.     

Looking for the best modes helps solving the MRCPSP/max

The multi-mode resource-constrained project scheduling problem with minimum and maximum time lags MRCPSP/max is a very general project scheduling problem with multiple execution modes per activity, renewable and non-renewable resources and minimum and maximum time lags between activities. In this paper, we describe SA-EVA, an algorithm for the problem. SA-EVA first searches for the best mode for each activity, without considering renewable resources. In this phase a simulated annealing is applied. Once a mode vector has been chosen, the problem reduces to the RCPSP/max, which SA-EVA solves with EVA, an algorithm designed in Ballestín et al. [2009. An evolutionary algorithm for the resource-constrained project scheduling problem with minimum and maximum time-lags. Journal of Scheduling, 14 (4), online]. Computational results show that SA-EVA outperforms the state-of-the-art algorithms in medium and large instances.     

A duplication heuristic for static scheduling of tasks on distributed memory multiprocessors

Abstract

A task duplication heuristic, DSH, was proposed in [11]. The underlying concept of the task duplication heuristic is duplicating some tasks on processors such that the earliest start time of tasks on processors can be reduced, that is, tasks on processors can be executed sooner. This leads to a better scheduling length. In this paper, we propose a more general task duplication heuristic, bottom‐up top‐down duplication heuristic (BTDH), for static scheduling of directed‐acyclic graphs (DAGs) on distributed memory multiprocessors. The key difference between BTDH and DSH is the method used for duplicating tasks. BTDH allows tasks to be duplicated on processors even though the duplication of tasks will temporarily increase the earliest start time of some tasks. DSH only allows those duplications which will reduce the earliest start time of tasks. Simulation results show that, for coarse‐grain DAGs, the scheduling length of BTDH is almost the same as the scheduling length of DSH. However, for medium‐grain and fine‐grain DAGs, BTDH produces better scheduling length than DSH.     

The resource renting problem subject to temporal constraints

We introduce a project scheduling problem subject to temporal constraints where the resource availability costs have to be minimized. As an extension of known project scheduling problems which consider only time-independent costs, this problem includes both time-independent procurement costs and time-dependent renting costs for the resources. Consequently, in addition to projects where all resources are bought, we can deal with projects where resources are rented. Based on the enumeration of a finite set of schedules which is proved to contain an optimal schedule, we develop a depth-first branch-and-bound procedure. Computational experience with a randomly generated test set containing 10800 problem instances is reported.

---

---

Received: December 1, 1999 / Accepted: November 8, 2000     

Scheduling two identical parallel machines with preparation constraints

In this paper, we consider the problem of scheduling a set of n jobs on two identical machines with preparation constraints. Each job requires before its execution a set of resources and a non-negligible preparation time. The objective is to minimise the makespan. This problem is NP-hard. We prove the NP-hardness of two specific cases where in the first case preparation times take only three values, whereas in the second case preparation times and the release dates take only two values, respectively. Then, we present some special cases and heuristic algorithms along with an experimental study.     

Minimising the makespan in the two-machine job shop problem under availability constraints

Classical scheduling problem assumes that machines are available during the scheduling horizon. This assumption may be justified in some situations but it does not apply if maintenance requirements, machine breakdowns or other availability constraints have to be considered. In this paper, we treat a two-machine job shop scheduling problem with one availability constraint on each machine to minimise the maximum completion time (makespan). The unavailability periods are known in advance and the processing of an operation cannot be interrupted by an unavailability period (non-preemptive case). We present in our approach properties dealing with permutation dominance and the optimality of Jackson's rule under availability constraints. In order to evaluate the effectiveness of the proposed approach, we develop two mixed integer linear programming models and two schemes for a branch and bound method to solve the tackled problem. Computational results validate the proposed approach and prove the efficiency of the developed methods.     

Models,algorithms and performance analysis for adaptive operating room scheduling

The complex optimisation problems arising in the scheduling of operating rooms have received considerable attention in recent scientific literature because of their impact on costs, revenues and patient health. For an important part, the complexity stems from the stochastic nature of the problem. In practice, this stochastic nature often leads to schedule adaptations on the day of schedule execution. While operating room performance is thus importantly affected by such adaptations, decision-making on adaptations is hardly addressed in scientific literature. Building on previous literature on adaptive scheduling, we develop adaptive operating room scheduling models and problems, and analyse the performance of corresponding adaptive scheduling policies. As previously proposed (fully) adaptive scheduling models and policies are infeasible in operating room scheduling practice, we extend adaptive scheduling theory by introducing the novel concept of committing. Moreover, the core of the proposed adaptive policies with committing is formed by a new, exact, pseudo-polynomial algorithm to solve a general class of stochastic knapsack problems. Using these theoretical advances, we present performance analysis on practical problems, using data from existing literature as well as real-life data from the largest academic medical centre in The Netherlands. The analysis shows that the practically feasible, basic, 1-level policy already brings substantial and statistically significant improvement over static policies. Moreover, as a rule of thumb, scheduling surgeries with large mean duration or standard deviation early appears good practice.     

Resources assignment model in maintenance activities scheduling

This paper proposes an analytical model for resources assignment in the context of maintenance activities scheduling. It takes into account the human as well as material resources availability constraints. It allows the decision maker to consider not only the preventive maintenance activities but also the potential failures which may occur during the scheduling horizon. Opportunistic maintenance may be considered as an option to improve the occupational rate mainly for maintenance operators. Additional constraints such as the completion time of some specific maintenance activities and the earliest starting works on a given machine may easily be considered in the model. Recall that the main purpose of this paper is to suggest an improved model for resources assignment to be implemented into a planning and scheduling module in CMMS software. The proposed model generates a feasible plan and makes sensitivity analysis possible in order to take into account the material and human resources fluctuations. A numerical example has been treated in order to illustrate the modelling process and to validate the coherence of the model. An attempt is made to develop a generic model which must be flexible and user friendly. Authors are investigating many other extensions of this work to fulfil some specific needs for the company which develops CMMS software. For the illustrative example presented in this paper, the explicit form of the mathematical model is provided in the Appendix of the paper.     

Extending the boundaries between scheduling and dispatching: hedging and rescheduling techniques

While deterministic scheduling models have been well studied, the use of these models is not well documented in manufacturing environments. Previous research has indicated that deterministic scheduling approaches quickly lose their advantage compared to dispatching rules when processing time uncertainty is present. This research presents the case of a Printed Wiring Board Manufacturer’s drilling operation, which is a group of unrelated parallel machines. The manufacturer wishes to minimise makespan, number of late jobs, total overtime, average machine finishing time and machine utilisation when stochastic uncertainty is present. While deterministic scheduling has been shown to be a good solution approach when processing time variability is low, this research attempts to extend the boundaries in which scheduling is useful by investigating job and machine hedges as well as periodic and event driven rescheduling policies. The success of the approach is evaluated using a simulation model to evaluate the performance over a number of sequential schedules under various distributional assumptions.     

PPT: A parallel programming tool for distributed memory multiprocessors

Abstract

Traditionally, to program a distributed memory multiprocessor, a programmer is responsible for partitioning an application program into modules or tasks, scheduling tasks on processors, inserting communication primitives, and generating parallel codes for each processor manually. As both the number of processors and the complexity of problems to be solved increases, programming distributed memory multiprocessors becomes difficult and error‐prone. In a distributed memory multiprocessor, the program partitioning and scheduling play an important role in the performance of a parallel program. However, how to find the best program partitioning and scheduling so that the best performance of a parallel program on a distributed memory multiprocessor can be achieved, is not an easy task. In this paper, we present a parallel programming tool, PPT, to aid programmers to find the best program partitioning and scheduling and automatically generate the parallel code for the single program multiple data (SPMD) model on a distributed memory multiprocessor. An example of designing a parallel FFT program by using PPT on an NCUBE‐2 is also presented.     

Assessing scheduling policies in a permutation flowshop with common due dates

This paper focuses onto a situation arising in most real-life manufacturing environments when scheduling has to be performed periodically. In such a scenario, different scheduling policies can be adopted, being perhaps the most common to assume that, once a set of jobs has been scheduled, their schedule cannot be modified (‘frozen’ schedule). This implies that, when the next set of jobs is to be scheduled, the resources may not be fully available. Another option is assuming that the schedule of the previously scheduled jobs can be modified as long as it does not violate their due date, which has been already possibly committed to the customer. This policy leads to a so-called multi-agent scheduling problem. The goal of this paper is to discern when each policy is more suitable for the case of a permutation flowshop with common due dates. To do so, we carry out an extensive computational study in a test bed specifically designed to control the main factors affecting the policies, so we analyse the solution space of the underlying scheduling problems. The results indicate that, when the due date of the committed jobs is tight, the multi-agent approach does not pay off in view of the difficulty of finding feasible solutions. Moreover, in such cases, the policy of ‘freezing’ the schedule of the jobs leads to a very simple scheduling problem with many good/acceptable solutions. In contrast, when the due date has a medium/high slack, the multi-agent approach is substantially better. Nevertheless, in this latter case, in order to perceive the full advantage of this policy, powerful solution procedures have to be designed, as the structure of the solution space of the latter problem makes extremely hard to find optimal/good solutions.     

A new complexity proof for the two-stage hybrid flow shop scheduling problem with dedicated machines

This paper considers a two-stage hybrid flow shop scheduling problem with dedicated machines at stage 2. The objective is to minimise the makespan. There is one machine at stage 1 and two machines at stage 2. Each job must be processed on the single machine at stage 1 and, depending upon the job type, the job is processed on either of the two machines at stage 2. We first introduce this special type of the two-stage hybrid flow shop scheduling problem and present some preliminary results. We then present a counter example to the known complexity proof of Riane et al. [Riane, F., Artiba, A. and Elmaghraby, S.E., 2002. Sequencing a hybrid two-stage flowshop with dedicated machines. International Journal of Production Research, 40, 4353–4380.] Finally, we re-establish the complexity of the problem.     

Minimising maximum tardiness in assembly flowshops with setup times

This paper addresses a two-stage assembly flowshop scheduling problem with the objective of minimising maximum tardiness where set-up times are considered as separate from processing times. The performance measure of maximum tardiness is important for some scheduling environments, and hence, it should be taken into account while making scheduling decisions for such environments. Given that the problem is strongly NP-hard, different algorithms have been proposed in the literature. The algorithm of Self-Adaptive Differential Evolution (SDE) performs as the best for the problem in the literature. We propose a new hybrid simulated annealing and insertion algorithm (SMI). The insertion step, in the SMI algorithm, strengthens the exploration step of the simulated annealing algorithm at the beginning and reinforces the exploitation step of the simulated annealing algorithm towards the end. Furthermore, we develop several dominance relations for the problem which are incorporated in the proposed SMI algorithm. We compare the performance of the proposed SMI algorithm with that of the best existing algorithm, SDE. The computational experiments indicate that the proposed SMI algorithm performs significantly better than the existing SDE algorithm. More specifically, under the same CPU time, the proposed SMI algorithm, on average, reduces the error of the best existing SDE algorithm over 90%, which indicates the superiority of the proposed SMI algorithm.     

Synchronisation of scarce resources for a parallel machine lotsizing problem

In this paper we present a novel approach to tackling the synchronisation of a secondary resource in lot-sizing and scheduling problems. This kind of problem occurs in various manufacturing processes (e.g. wafer testing in the semiconductor industry, production and bottling of soft drinks). We consider a scenario of parallel unrelated machines that have to be equipped with a tool or need a special kind of resource for processing. Our approach allows tracing the assignment of these secondary resources across different machines and synchronising their usage independently of the time period. We present extensions of the general lot-sizing and scheduling problem and of the capacitated lot-sizing problem. We prove that the latter model is a special case of the first, but it performs computationally much better.     

Robust multi-objective optimization for energy production scheduling in microgrids

In order to achieve better economic and environmental benefits of microgrids (MGs) under multiple uncertainties in renewable energy resources and loads, a novel energy production scheduling method is proposed based on robust multi-objective optimization with minimax criterion. Firstly, a mixed integer minimax multi-objective formulation is developed to capture uncertainties as well as minimize economic and environmental objectives. Secondly, the primal problem is decomposed into a bi-level optimization problem, which attempts to seek robust scheduling scheme set under the worst-case realization of uncertainties in a multi-objective framework. Finally, a hierarchical meta-heuristic solution strategy, including multi-objective cross entropy algorithm and δ+ indicator, is designed to solve the reconstructed problem. Numerical results demonstrate that the proposed scheduling method can effectively attenuate the disturbance of uncertainties as well as reduce energy costs and emissions, as compared with single-objective robust optimization and multi-objective optimization scheduling approaches. This study could offer useful insights which help decision-makers balance robustness and comprehensive benefits in the operation of MGs.     

A CTPN‐based scheduler for a flexible manufacturing cell

Abstract

This paper first presents hierarchical scheduling and control architecture for a flexible manufacturing cell (FMC) that is currently set up at the Mechanical Industrial Research Laboratories of the Industrial Technology Research Institute at Hsinchu, Taiwan. With this architecture, we focus on the scheduling problem of the FMC and present a scheduling mechanism based on a colored timed Petri net (CTPN) model. The CTPN model has three functions in the proposed mechanism: the first one is to formally describe pallet flows and resource constraints in the FMC by the event‐condition relation; the second one is to analyze conflict points among the pallet flows; the third one is to evaluate the used dispatching rules concerned with the selection of machine routings, the selection of work‐in‐process pallets in inter‐medium buffers and the assignment of the commonly used material‐handling device. Using the CTPN‐based scheduler, an appropriate combination of dispatching rules for each given batch can be selected to fit given criteria, e.g. minimum batch completion time, maximum resource utilization or minimum tardiness, etc. Moreover, real‐time status of the FMC can be represented in the mechanism for obtaining the on‐line scheduling effect.     

An immune algorithm for scheduling a hybrid flow shop with sequence-dependent setup times and machines with random breakdowns

Much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. Furthermore, most scheduling problems that have been discussed in the literature are under the assumption that machines are continuously available. Nevertheless, in most real-life industries a machine can be unavailable for many reasons, such as unanticipated breakdowns (stochastic unavailability), or due to scheduled preventive maintenance where the periods of unavailability are known in advance (deterministic unavailability). This paper deals with hybrid flow shop scheduling problems in which there are sequence-dependent setup times (SDSTs), and machines suffer stochastic breakdowns, to optimise objectives based on the expected makespan. With the increase in manufacturing complexity, conventional scheduling techniques for generating a reasonable manufacturing schedule have become ineffective. An immune algorithm (IA) can be used to tackle complex problems and produce a reasonable manufacturing schedule within an acceptable time. In this research, a computational method based on a clonal selection principle and an affinity maturation mechanism of the immune response is used. This paper describes how we can incorporate simulation into an immune algorithm for the scheduling of a SDST hybrid flow shop with machines that suffer stochastic breakdowns. The results obtained are analysed using a Taguchi experimental design.     

A New Task Scheduling Scheme Based on Genetic Algorithm for Edge Computing

With the continuous evolution of smart grid and global energy interconnection technology, amount of intelligent terminals have been connected to power grid, which can be used for providing resource services as edge nodes. Traditional cloud computing can be used to provide storage services and task computing services in the power grid, but it faces challenges such as resource bottlenecks, time delays, and limited network bandwidth resources. Edge computing is an effective supplement for cloud computing, because it can provide users with local computing services with lower latency. However, because the resources in a single edge node are limited, resource-intensive tasks need to be divided into many subtasks and then assigned to different edge nodes by resource cooperation. Making task scheduling more efficient is an important issue. In this paper, a two-layer resource management scheme is proposed based on the concept of edge computing. In addition, a new task scheduling algorithm named GA-EC(Genetic Algorithm for Edge Computing) is put forth, based on a genetic algorithm, that can dynamically schedule tasks according to different scheduling goals. The simulation shows that the proposed algorithm has a beneficial effect on energy consumption and load balancing, and reduces time delay.