Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is N P‐hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst‐case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two‐machine flow shop and the open shop problems with a single server are also shown to be N P‐hard in the strong sense. However, we reduce the two‐machine flow shop no‐wait problem with a single server to the Gilmore—Gomory traveling salesman problem and solve it in polynomial time. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304–328, 2000     

Note: On the two‐machine no‐idle flowshop problem

In this short note we study a two‐machine flowshop scheduling problem with the additional no‐idle feasibility constraint and the total completion time criterion function. We show that one of the few papers which deal with this special problem contains incorrect claims and suggest a way how these claims can be rectified. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47:353–358, 2000     

Heuristic procedures for scheduling job families with setups and due dates

This paper examines heuristic solution procedures for scheduling jobs on a single machine to minimize the maximum lateness in the presence of setup times between different job families. It reviews the state of knowledge about the solution of this problem, which is known to be difficult to solve in general, and examines natural solution approaches derived from some of the underlying theory. The emphasis is on the design and computational evaluation of new heuristic procedures. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 978–991, 1999     

Local search methods for the discrete time/resource trade-off problem in project networks

In this paper we consider the discrete time/resource trade-off problem in project networks. Given a project network consisting of nodes (activities) and arcs (technological precedence relations), in which the duration of the activities is a discrete, nonincreasing function of the amount of a single renewable resource committed to it, the discrete time/resource trade-off problem minimizes the project makespan subject to precedence constraints and a single renewable resource constraint. For each activity, a work content is specified such that all execution modes (duration/resource requirement pairs) for performing the activity are allowed as long as the product of the duration and the resource requirement is at least as large as the specified work content. We present a tabu search procedure which is based on a decomposition of the problem into a mode assignment phase and a resource-constrained project scheduling phase with fixed mode assignments. Extensive computational experience, including a comparison with other local search methods, is reported. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 553–578, 1998     

Scheduling to minimize the total compression and late costs

We consider a single-machine scheduling model in which the job processing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job processing times and the cost associated with the number of late jobs. The problem is shown to be NP-hard even when the due dates of all jobs are identical. We present a dynamic programming solution algorithm and a fully polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experiments demonstrate that the heuristics are capable of producing near-optimal solutions quickly. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 67–82, 1998     

Minimizing weighted earliness and tardiness penalties in single‐machine scheduling with idle time permitted

In this paper, a single‐machine scheduling problem with weighted earliness and tardiness penalties is considered. Idle time between two adjacent jobs is permitted and due dates of jobs could be unequal. The dominance rules are utilized to develop a relationship matrix, which allows a branch‐and‐bound algorithm to eliminate a high percentage of infeasible solutions. After combining this matrix with a branching strategy, a procedure to solve the problem is proposed. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 760–780, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10039     

Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints

In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016     

A bidirectional heuristic for maximizing the net present value of large‐scale projects subject to limited resources

We consider the scheduling of large‐scale projects to maximize the project net present value given temporal and resource constraints. The net present value objective emphasizes the financial aspects of project management. Temporal constraints between the start times of activities make it possible to handle practical problem assumptions. Scarce resources are an expression of rising cost. Since optimization techniques are not expedient to solve such problems and most heuristic methods known from literature cannot deal with general temporal constraints, we propose a new bidirectional priority‐rule based method. Scheduling activities with positive cash flows as early and activities with negative cash flows as late as possible results in a method which is completed by unscheduling techniques to cope with scarce resources. In a computational experiment, we compare the well‐known serial generation scheme where all activities are scheduled as early as possible with the proposed bidirectional approach. On the basis of a comprehensive data set known from literature containing instances with up to 1002 activities, the efficiency of the new approach is demonstrated. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Replacing nonidentical vital components to extend system life

We consider a system that depends on a single vital component. If this component fails, the system life will terminate. If the component is replaced before its failure then the system life may be extended; however, there are only a finite number of spare components. In addition, the lifetimes of these spare components are not necessarily identically distributed. We propose a model for scheduling component replacements so as to maximize the expected system survival. We find the counterintuitive result that when comparing components' general lifetime distributions based on stochastic orderings, not even the strongest ordering provides an a priori guarantee of the optimal sequencing of components. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008