An evaluation of heuristics for scheduling a non-delay permutation flow shop with family setups to minimize total earliness and tardiness

This paper presents several procedures for developing non-delay schedules for a permutation flow shop with family setups when the objective is to minimize total earliness and tardiness. These procedures consist of heuristics that were found to be effective for minimizing total tardiness in flow shops without family setups, modified to consider family setups and the total earliness and tardiness objective. These procedures are tested on several problem sets with varying conditions. The results show that variable greedy algorithms are effective when solving small problems, but using a genetic algorithm that includes a neighbourhood defined by the sequence of batches of jobs belonging to the same set-up family is effective when solving medium- or large-sized problems. The results also show that if setup times can be reduced a significant reduction in total earliness and tardiness could result.     

An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances

In this paper, an overview is presented of the existing metaheuristic solution procedures to solve the multi-mode resource-constrained-project scheduling problem, in which multiple execution modes are available for each of the activities of the project. A fair comparison is made between the different metaheuristic algorithms on the existing benchmark datasets and on a newly generated dataset. Computational results are provided and recommendations for future research are formulated.     

Experimental investigation of heuristics for resource-constrained project scheduling: An update

This paper considers heuristics for the well-known resource-constrained project scheduling problem (RCPSP). It provides an update of our survey which was published in 2000. We summarize and categorize a large number of heuristics that have recently been proposed in the literature. Most of these heuristics are then evaluated in a computational study and compared on the basis of our standardized experimental design. Based on the computational results we discuss features of good heuristics. The paper closes with some remarks on our test design and a summary of the recent developments in research on heuristics for the RCPSP.     

Proactive heuristic procedures for robust project scheduling: An experimental analysis

Solution-robust project scheduling is a growing research field aiming at constructing proactive schedules to cope with multiple disruptions during project execution. When stochastic activity durations are considered, including time buffers between activities is a proven method to improve the stability of a baseline schedule.     

An investigation of buffer sizing techniques in critical chain scheduling

In this paper, we introduce two methods for determining feeding buffer sizes in critical chain project scheduling. Both methods integrate project characteristics into the formulation. Specifically, one of them incorporates resource tightness while the other uses network complexity. Both methods are tested and compared to two commonly suggested methods in the literature, the cut and paste method and the root square error method, as well as using no buffer as a benchmark. The comparison is done by means of a simulation study using the Patterson data set. The test results indicate that both of the suggested methods generate smaller buffer sizes while providing sufficient protection against delays in project completion time.     

Voter turnout as a participation game: An experimental investigation

Financial support by the Netherlands' Organization for Scientific Research (NWO) is gratefully acknowledged. We would like to thank Jeff Banks, Eric van Damme, Werner Güth, Claudia Keser, Theo Offerman, Mark Olson, J?rgen Wit, and two anonymous referees for useful comments, and Otto Perdeck for computational assistance.     

Starting-time decisions in labor tour scheduling: An experimental analysis and case study

Many service organizations limit the number of daily planning periods in which employees may begin their shifts to a fixed number, S. Even for relatively small values of S, which are quite common in practice, there may be hundreds, thousands or millions of possible subsets of starting times. This paper presents the results of a large experimental study that revealed that, in many instances, only a very small portion of starting-time subsets was capable of providing the minimum workforce size. The importance of effective starting-time selection is further supported by a case study that describes a spreadsheet-based program designed for scheduling customer service representatives in the System Support Center, United States and Canada Group, Radio Network Solutions Group, Land Mobile Products Sector, Motorola.     

Entry coordination in auctions and social welfare: An experimental investigation

Most of the literature on auctions with endogenous entry assumes that, in equilibrium, the number of entrants is deterministic. We discuss a series of experiments designed to test the alternative hypothesis that, even in equilibrium, the number of entrants is stochastic. This distinction has strong implications for auction performance, the design of optimal mechanisms, and social welfare. Our results strongly reject the hypothesis of deterministic entry and tend to confirm the alternative hypothesis that entry is stochastic. Revised February 2000     

Decentralized versus collective bargaining – An experimental study

Two parties X, and Y, can either bargain separately with a third party Z or merge to become XY and bargain collectively with Z. Depending on the payoff implications of the two possible contracts and on the asymmetry inherent in the conflict payoffs of X and Y collective bargaining will increase, decrease or leave constant what X and Y achieve together. In the experiment, first X and Y vote for or against collective bargaining and then negotiate accordingly. Participants react adequately to strategic aspects, but not as predicted by the (Nash-)bargaining solution. Received: April 2000/Final version: December 2001     

On distributed scheduling with heterogeneously delayed network-state information

We study the problem of distributed scheduling in wireless networks, where each node makes individual scheduling decisions based on heterogeneously delayed network state information (NSI). This leads to inconsistency in the views of the network across nodes, which, coupled with interference, makes it challenging to schedule for high throughputs. We characterize the network throughput region for this setup, and develop optimal scheduling policies to achieve the same. Our scheduling policies have a threshold-based structure and, moreover, require the nodes to use only the “smallest critical subset” of the available delayed NSI to make decisions. In addition, using Markov chain mixing techniques, we quantify the impact of delayed NSI on the throughput region. This not only highlights the value of extra NSI for scheduling, but also characterizes the loss in throughput incurred by lower complexity scheduling policies which use homogeneously delayed NSI.     

The resource-constrained modulo scheduling problem: an experimental study

In this paper, we focus on the resource-constrained modulo scheduling problem (RCMSP), a general periodic scheduling problem, abstracted from the problem solved by compilers when optimizing inner loops at instruction level for VLIW parallel processors. Heuristic solving scheme have been proposed since many years to solve this problem, among which the decomposed software pipeling method. In this method, a cyclic scheduling problem ignoring resource constraints is first considered and a so-called legal retiming of the operations is issued. Second, a standard acyclic problem, taking this retiming as input, is solved through list scheduling techniques. In this paper, we propose a novel hybrid approach, which uses the decomposed software pipeling method to obtain a good retiming. Then the obtained retiming is used to build an integer linear programming formulation of reduced size, which allows to solve it exactly. Experimental results show that a lot more problems are solved with this new approach. The gap to the optimal solution is less than 1 % on most of the tested problem instances and the method appears to be competitive with a recently proposed constraint programming algorithm (Bonfietti et al., Lect. Notes Comput. Sci. 6876:130–144, 2011).     

An acyclic days-off scheduling problem

This paper studies the days off scheduling problem when the demand for staffing fluctuates from day to another and when the number of total workdays is fixed in advance for each employee. The scheduling problem is then to allocate rests to employees with different days off policies: (1) two or three consecutive days off for each employee per week and (2) at least three consecutive days off for each employee per month. For each one, we propose a polynomial time algorithm to construct a solution if it exists. Received: April 2005 / Revised version: October 2005 AMS classification: 60K25, 60K30     

Experimental investigation of real-time scheduling in flexible manufacturing systems

This paper presents a new two-phase (TP) approximate method for real-time scheduling in a flexible manufacturing system (FMS). This method combines a reduced enumeration schedule generation algorithm with a 0–1 optimization algorithm. In order to make the combined algorithm practicable, heuristic rules are introduced for the selection of jobs to be scheduled. The relative performance of the TP method vis-a-vis conventional heuristic dispatching rules such as SPT, LPT, FCFS, MWKR, and LWKR is investigated using combined process-interaction/discrete-event simulation models. An efficient experimental procedure is designed and implemented using these models, and the statistical analysis of the results is presented. For the particular case investigated, the conclusions are very encouraging. In terms of mean flow time, the TP method performs significantly better than any other tested heuristic dispatching rules. Also, the experimental results show that using global information significantly improves the FMS performance.     

堆取料机调度问题的一个近似算法

研究源自煤炭港口料场管理的堆取料机调度问题.该问题中,堆取料机从长为L的料场作业区最左端开始空机或载料运行,两者的速度之比为s：1（s ≥ 1）.决策者需确定储料堆在作业区的分布以及堆取料机处理它们的先后次序,目的是极小化一批煤料运输船的在港服务时间.考虑堆取料机处理完毕需要回到料场终端的作业模型,证明了存在最坏情况界不超过1+1/4s的近似算法.     

Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors

This paper investigates the computational complexity of preemptive and nonpreemptive scheduling of biprocessor tasks on dedicated processors in general and some of its special cases. We consider two criteria of optimality: the schedule length and sum of task completion times. In addition, we analyze the complexity of these problems when precedence constraints are involved. We show that in general all these problems are NP-hard in the strong sense.     

Focused simulated annealing search: An application to job shop scheduling

This paper presents a simulated annealing search procedure developed to solve job shop scheduling problems simultaneously subject to tardiness and inventory costs. The procedure is shown to significantly increase schedule quality compared to multiple combinations of dispatch rules and release policies, though at the expense of intense computational efforts. A meta-heuristic procedure is developed that aims at increasing the efficiency of simulated annealing by dynamically inflating the costs associated with major inefficiencies in the current solution. Three different variations of this procedure are considered. One of these variations is shown to yield significant reductions in computation time, especially on problems where search is more likely to get trapped in local minima. We analyze why this variation of the meta-heuristic is more effective than the others.     

An experimental and computational investigation of crack initiation and stable crack growth of ductile materials

Crack initiation and stable crack growth under monotonic loading in steels has been studied using an elastic-plastic finite element analysis. The fracture criterion used for crack initiation and stable crack growth was the critical strain energy density. In addition the shift core method for the analysis of crack extension was used. In the shift core modelling method, crack advance is simulated by moving the coordinates of the core region which surrounds the crack tip, to obtain the stiffness reduction. Simultaneously the core itself geometrically undergoes a simple rigid-body motion or translation during the crack extension. The analytically calculated and experimentally measured load for crack initiation and the subsequent stable crack growth agreed well.     

An evolutionary approach to rehabilitation patient scheduling: A case study

Focusing on real settings, this study aimed to develop an evolutionary approach based on genetic algorithm for solving the problem of rehabilitation patient scheduling to increase service quality by reducing patient waiting time and improve operation efficiency by increasing the therapy equipment utilization. Indeed, due to partial precedence constraints of rehabilitation therapies, the problem can be structured as a hybrid shop scheduling problem that has received little attention to date. In addition, a mixed integer programming model was also constructed as a benchmark to validate the solution quality with small problems. Based on empirical data from a Medical Center in Taiwan, several experiments were conducted to estimate the validity of the proposed algorithm. The results showed that the proposed algorithm can reduce patient waiting time and enhance resource utilization and thus demonstrated the practicality of the proposed algorithm. Indeed, a decision support system embedded with the developed algorithm has been implemented in this medical center.     

Improvement heuristic for the flow-shop scheduling problem: An adaptive-learning approach

We propose an improvement-heuristic approach for the general flow-shop problem (n/m/C_max) based on the idea of adaptive learning. The approach employs a one-pass heuristic to give a good starting solution in the search space and uses a weight parameter to perturb the data of the original problem to obtain improved solutions. The weights are then adjusted employing a learning strategy which involves reinforcement and backtracking. The learning is similar to that in neural networks. The random perturbation allows a non-deterministic local search. We apply the improvement-heuristic approach in conjunction with three well-known heuristics in the literature, namely, Palmer’s Slope Index, CDS and NEH. We test our approach on several benchmark problem sets including Taillard’s, Carlier’s, Heller’s and Reeves’. We compare our results to the best-known upper-bound solutions and find that for many problems we match the best-known upper bound. For one problem we discover a new upper bound.