A note on resource allocation scheduling with group technology and learning effects on a single machine

In this article, single-machine group scheduling with learning effects and convex resource allocation is studied. The goal is to find the optimal job schedule, the optimal group schedule, and resource allocations of jobs and groups. For the problem of minimizing the makespan subject to limited resource availability, it is proved that the problem can be solved in polynomial time under the condition that the setup times of groups are independent. For the general setup times of groups, a heuristic algorithm and a branch-and-bound algorithm are proposed, respectively. Computational experiments show that the performance of the heuristic algorithm is fairly accurate in obtaining near-optimal solutions.     

Improved imperialist competitive algorithms for rebalancing multi-objective two-sided assembly lines with space and resource constraints

In this paper, a mathematical model and an improved imperial competition algorithm (IICA) are proposed to solve the multi-objective two-sided assembly line rebalancing problem with space and resource restrictions (MTALRBP-SR). The aim is to find lines’ rebalance with the trade-off between efficiency, rebalancing cost and smoothing after reconfiguration. IICA utilises a new initialisation heuristic procedure based on classic heuristic rules to generate feasible initial solutions. A novel heuristic assimilation method is developed to vigorously conduct local search. In addition, a group-based decoding heuristic procedure is developed to fulfil the final task reassignment with the additional restrictions. To investigate the performance of the proposed algorithm, it is first tested on MTALRBP of benchmark problems and compared with some existing algorithms such as genetic algorithm, variable neighbourhood search algorithm, discrete artificial bee colony algorithm, and two iterated greedy algorithms. Next, the efficiency of the proposed IICA for solving MTALRBP-SR is revealed by comparison with a non-dominated sorting genetic algorithm (NSGA-II) and two versions of original ICA. Computational results and comparisons show the efficiency and effectiveness of IICA. Furthermore, a real-world case study is conducted to validate the proposed algorithm.     

A constraint-based perspective in resource constrained project scheduling

In this study, a new heuristic approach to the resource constrained project scheduling problem is introduced. This approach, which is called local constraint based analysis (LCBA), is more robust than the dispatching rules found in the literature, since it does not depend on an a priori insight as do the dispatching rules. LCBA consists of the application of local essential conditions which respect the current temporal and resource constraints to generate a necessary sequence of activities at a scheduling decision time point in a single-pass parallel scheduling algorithm. LCBA is a time efficient procedure due to the localized aspect with which the activities are handled. Only the activities which are schedulable at the current scheduling time are considered for the application of the essential conditions. LCBA is tested against well-known rules from the literature and some recently developed rules. This testing is done using a set of problems of a special design and also a set of optimally solved problems from a recent benchmark in the literature. It is observed that near optimal time efficient solutions are obtained by LCBA and the procedure's performance is considerably better than that of the dispatching rules.     

The integration of resource allocation and time buffering for bi-objective robust project scheduling

In the recent decades, the recognition that uncertainty lies at the heart of modern project management has induced considerable research efforts on robust project scheduling for dealing with uncertainty in a scheduling environment. The literature generally provides two main strategies for the development of a robust predictive project schedule, namely robust resource allocation and time buffering. Yet, the previous studies seem to have neglected the potential benefits of an integration between the two. Besides, few efforts have been made to protect simultaneously the project due date and the activity start times against disruptions during execution, which is desperately demanded in practice. In this paper, we aim at constructing a proactive schedule that is not only short in time but also less vulnerable to disruptions. Firstly, a bi-objective optimisation model with a proper normalisation of the two components is proposed in the presence of activity duration variability. Then a two-stage heuristic algorithm is developed which deals with a robust resource allocation problem in the first stage and optimally determines the position and the size of time buffers using a simulated annealing algorithm in the second stage. Finally, an extensive computational experiment on the PSPLIB network instances demonstrates the superiority of the combination between resource allocation and time buffering as well as the effectiveness of the proposed two-stage algorithm for generating proactive project schedules with composite robustness.     

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.     

A heuristic for designing manufacturing focus units with resource considerations

This paper presents a model of the plant-within-a-plant (PWP) design problem and demonstrates a heuristic for analysing the problem. Although the benefits of a manufacturing focus have been articulated in the literature, methods for implementation with consideration for resource requirements have not been developed previously. In this study, we discuss the importance of including resource considerations and propose a methodology that can help managers arrive at a facility design with a high degree of focus and minimum resource needs. A heuristic is developed that incorporates the concept of order-winning criteria and volume into the focus design. The heuristic not only recognises the effects of conflicting manufacturing tasks, but also considers resource costs and material flows between PWP units. Experimental results show that the proposed methodology offers managers the opportunity to generate and assess alternative PWP designs, which are otherwise unavailable. Overall, this research provides an analytical framework for further research in focused manufacturing.     

A parallel machine lot-sizing and scheduling problem with a secondary resource and cumulative demand

We investigate a parallel machine multi-item lot-sizing and scheduling problem with a secondary resource, in which demands are given for the entire planning horizon rather than for every single period. All-or-nothing assumption of the discrete lot-sizing and scheduling problem is valid so that a machine is either idle or works at full capacity in a period. The objective is to minimise the number of setups and teardowns. We prove that the problem is NP-hard and present two equivalent formulations. We show some properties of the optimal objective value, give optimality conditions and suggest a heuristic algorithm. We discuss and formulate two possible extensions related to real-life applications. Finally, we carry out computational experiments to compare the two formulations, to determine the effect of our proposed modeling improvements on solution performance, and to test the quality of our heuristic.     

A heuristic model for dynamic flexible job shop scheduling problem considering variable processing times

In real scheduling problems, unexpected changes may occur frequently such as changes in task features. These changes cause deviation from primary scheduling. In this article, a heuristic model, inspired from Artificial Bee Colony algorithm, is proposed for a dynamic flexible job-shop scheduling (DFJSP) problem. This problem consists of n jobs that should be processed by m machines and the processing time of jobs deviates from estimated times. The objective is near-optimal scheduling after any change in tasks in order to minimise the maximal completion time (Makespan). In the proposed model, first, scheduling is done according to the estimated processing times and then re-scheduling is performed after determining the exact ones considering machine set-up. In order to evaluate the performance of the proposed model, some numerical experiments are designed in small, medium and large sizes in different levels of changes in processing times and statistical results illustrate the efficiency of the proposed algorithm.     

Flexible job-shop scheduling with flexible workdays,preemption, overlapping in operations and satisfaction criteria: an industrial application

This paper addresses a real scheduling problem, namely, a complex flexible job-shop scheduling problem (FJSP) with special characteristics (flexible workdays, preemption and overlapping in operations), where the objective is to maximise a satisfaction criterion defined through goal programming. To allow for flexible workdays, the solution representation of the classical FJSP is extended to consider overtime decisions and a sequence of time-cell states, which is used to model resource capability. A new temporal-constraint-handling method is proposed to solve the problem of overlapping in operations in a flexible-workday environment. Three solution methods are proposed to solve this scheduling problem: a heuristic method based on priority rules, a goal-guided tabu search (GGTS) and an extended genetic algorithm (EGA). In the GGTS, the neighbourhood functions are defined based on elimination approaches, and five possible neighbourhood functions (N0???N1???N2???N3???N4) are presented. The effectiveness and efficiency of the three solution methods are verified using dedicated benchmark instances. Computational simulations and comparisons indicate that the proposed N4-based GGTS demonstrates performance competitive with that of the EGA and the GGTSs based on the other neighbourhood functions (N0, N1, N2 and N3) for solving the scheduling problem.     

Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes

The paper addresses minimizing makespan by a genetic algorithm (GA) for scheduling jobs with non-identical sizes on a single-batch-processing machine. A batch-processing machine can process up to B jobs simultaneously. The processing time of a batch is equal to the longest processing time among all jobs in the batch. Two different GAs are proposed based on different encoding schemes. The first is a sequence-based GA (SGA) that generates random sequences of jobs using GA operators and applies the batch first fit heuristic to group the jobs. The second is a batch-based hybrid GA (BHGA) that generates random batches of jobs using GA operators and ensures feasibility by using knowledge of the problem based on a heuristic procedure. A greedy local search heuristic based on the problem characteristics is hybridized with a BHGA that has the ability of steering efficiently the search toward the optimal or near-optimal schedules. The performance of proposed GAs is compared with a simulated annealing (SA) approach proposed by Melouk et al. (Melouk, S., Damodaran, P. and Chang, P.Y., Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. Int. J. Prod. Econ., 2004, 87, 141–147) and also against a modified lower bound proposed for the problem. Computational results show that BHGA performs considerably well compared with the modified lower bound and significantly outperforms the SGA and SA in terms of both quality of solutions and required runtimes.     

Re-entrant flow shop scheduling problem with time windows using hybrid genetic algorithm based on auto-tuning strategy

The re-entrant flow shop scheduling problem considering time windows constraint is one of the most important problems in hard-disc drive (HDD) manufacturing systems. In order to maximise the system throughput, the problem of minimising the makespan with zero loss is considered. In this paper, evolutionary techniques are proposed to solve the complex re-entrant scheduling problem with time windows constraint in manufacturing HDD devices with lot size. This problem can be formulated as a deterministic Fm?|?fmls, rcrc, temp?|?C_max problem. A hybrid genetic algorithm was used for constructing chromosomes by checking and repairing time window constraints, and improving chromosomes by a left-shift heuristic as a local search algorithm. An adaptive hybrid genetic algorithm was eventually developed to solve this problem by using fuzzy logic control in order to enhance the search ability of the genetic algorithm. Finally, numerical experiments were carried out to demonstrate the efficiency of the developed approaches.     

Column Generation Based Heuristic Algorithm for Multi-Item Scheduling

The column generation algorithm for the multi-item lot-size scheduling problem under resource constraints is examined and improved upon by augmenting simpler heuristic routines in place of the time-consuming Wagner-Whitin dynamic programming routine. The heuristic algorithms thus developed are tested by controlling problem size, setup time, demand variability, and capacity change costs in test problems. The empirical results indicate that the proposed heuristic algorithms reduce CPU time as well as the number of iterations with only a slight loss in optimality.     

Project scheduling with time-varying resource constraints

With industrial projects increasing in complexity and size, determining realizable schedules that efficiently utilize limited resources represents one of the most challenging project management tasks. In this context, the well-known resourceconstrained project scheduling problem has been extensively studied. However, due to its restrictive assumptions, it allows only partial modelling of real-world scheduling problems. Therefore, this paper deals with a generalized version that considers more evolved types of precedence relationships as well as time-varying resource availabilities, e.g. due to maintenance or vacations. For this problem, appropriate heuristic solution methods, based on priority rules and tabu search, are proposed and evaluated concerning their effectiveness.     

Ant colonies with cooperative process applied to the resource allocation problem

Abstract

In this paper, a novel algorithm describing ant colonies, with cooperation, is proposed to solve the resource allocation problem. The resource allocation problem is to allocate resources to activities, with the objective of optimizing the cost function. In our study, we viewed the search in ant colonies as a mechanism providing a main portion of diversity in search space. The cooperative process conducts fine‐tuning for the solution provided by ant colonies, and it has the ability to escape from poor local optima. In this paper, several examples are tested to prove the superiority of our proposed algorithm. From simulation results, the proposed algorithm indeed has remarkable performance.     

A simple and effective heuristic for the resource constrained project scheduling problem

This paper investigates the development and application of a simple heuristic to the resource constrained project scheduling problem (RCPSP). This computer heuristic, which is based on the COMSOAL heuristic, constructs a feasible solution at each iteration and chooses the best solution of several iterations. Although COMSOAL was originally a solution approach for the assembly-line balancing problem, it can be extended to provide solutions to the resource allocation problem. The Modified COMSOAL technique presented in this paper uses priority schemes intermittently with a random selection technique. This hybrid of randomness and priority scheme allows a good solution to be found quickly while not being forced into the same solution at each iteration. Several different priority schemes are examined within this research. The COMSOAL heuristic modified with the priority schemes heuristic was tested on several established test sets and the solution values are compared with both known optimal values and the results of several other resource allocation heuristics. In the vast majority of cases, the Modified COMSOAL heuristic outperformed the other heuristics in terms of both average and maximum percentage difference from optimal. The Modified COMSOAL heuristic seems to have several advantages over other RCPSP heuristics in that it is easy to understand, easy to implement, and achieves good results.     

Job shop scheduling with a combination of four buffering constraints

In this paper, a new scheduling problem is investigated in order to optimise a more generalised Job Shop Scheduling system with a Combination of four Buffering constraints (i.e. no-wait, no-buffer, limited-buffer and infinite-buffer) called CBJSS. In practice, the CBJSS is significant in modelling and analysing many real-world scheduling systems in chemical, food, manufacturing, railway, health care and aviation industries. Critical problem properties are thoroughly analysed in terms of the Gantt charts. Based on these properties, an applicable mixed integer programming model is formulated and an efficient heuristic algorithm is developed. Computational experiments show that the proposed heuristic algorithm is satisfactory for solving the CBJSS in real time.     

A bi-objective robust model for emergency resource allocation under uncertainty

Emergency resource allocation constitutes one of the most critical elements of response operations in the field of emergency management. This paper addresses an emergency resource allocation problem which involves multiple competing affected areas and one relief resource centre under supply shortage and uncertainty in the post-disaster phase. In humanitarian situations, both the efficiency and fairness of an allocation policy have a considerable influence on the effectiveness of emergency response operations. Thus, we formulate a bi-objective robust emergency resource allocation (BRERA) model which tries to maximise efficiency as well as fairness under different sources of uncertainties. To obtain decision-makers’ most preferred allocation policy, we propose a novel emergency resource allocation decision method which consists of three steps: (1) develop a bi-objective heuristic particle swarm optimisation algorithm to search the Pareto frontier of the BRERA model; (2) select a coefficient to measure fairness; and (3) establish a decision method based on decision-makers’ preference restricted by the fairness coefficient. Finally, a real case study taken from the 5 December 2008 Wenchuan Earthquake demonstrates the effectiveness of the proposed method through numerical results. The solution and model robustness are also analysed.     

Two level heuristic for the resource constrained scheduling problem

A two level heuristic for the resource constrained scheduling problem is presented. This heuristic is based on a combination of priority rules where utilization of resources by the operations, the critical path of operations in a job, and the due dates of the jobs are taken into account. The schedules that this heuristic generates have been compared with small problems for which optimal solutions are available and it is shown that these solutions are generally within 15% of the optimal. Also the polynomial time and space complexity of the heuristic is demonstrated.     

Scheduling in a cellular manufacturing system: a simulated annealing approach

The problem of scheduling in a cellular manufacturing system is considered with the objective of minimizing the sum of completion times (or total flow time) of jobs. A correct formulation of recursive equation for the flowline-based cellular manufacturing system is first proposed. Subsequently a heuristic is developed to obtain a sequence that minimizes total flow time in a flowline cell. The proposed heuristic makes use of the simulated annealing technique and is developed in two stages. A good initial heuristic seed sequence obtained in the first stage is improved upon by a proposed new variant of the simulated annealing technique wherein three different perturbation schemes have been experimented with. One of the perturbation schemes is newly proposed in this paper and is called the Adjacent interchange scheme. The proposed simulated annealing algorithm has been compared with the existing heuristics for minimizing flow time and has shown consistently good and superior solutions.     

Optimising resource portfolio planning for capital-intensive industries under process-technology progress

This paper addresses the problem of resource portfolio planning of firms in high-tech, capital-intensive manufacturing industries. In light of the strategic importance of resource portfolio planning in these industries, we offer an alternative approach to modelling capacity planning and allocation problems that improves the deficiencies of prior models in dealing with three salient features of these industries, i.e. fast technological obsolescence, volatile market demand, and high capital expenditure. This paper first discusses the characteristics of resource portfolio planning problems including capacity adjustment and allocation. Next, we propose a new mathematical programming formulation that simultaneously optimises capacity planning and task assignment. For solution efficiency, a constraint-satisfied genetic algorithm (CSGA) is developed to solve the proposed mathematical programming problem on a real-time basis. The proposed modelling scheme is employed in the context of a semiconductor testing facility. Experimental results show that our approach can solve the resource portfolio planning problem more efficiently than a conventional optimisation solver. The overall contribution is an analytical tool that can be employed by decision makers responding to the dynamic technological progress and new product introduction at the strategic resource planning level.