A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents

This paper addresses a two-agent scheduling problem on a single machine where the objective is to minimize the total weighted earliness cost of all jobs, while keeping the earliness cost of one agent below or at a fixed level Q. A mixed-integer programming (MIP) model is first formulated to find the optimal solution which is useful for small-size problem instances. To solve medium- to large-size problem instances, a branch-and-bound algorithm incorporating with several dominance properties and a lower bound is then provided to derive the optimal solution. A simulated annealing heuristic algorithm incorporating with a heuristic procedure is developed to derive the near-optimal solutions for the problem. A computational experiment is also conducted to evaluate the performance of the proposed algorithms.     

The total completion time open shop scheduling problem with a given sequence of jobs on one machine

This paper addresses the open shop scheduling problem to minimize the total completion time, provided that one of the machines has to process the jobs in a given sequence. The problem is NP-hard in the strong sense even for the two-machine case. A lower bound is derived based on the optimal solution of a relaxed problem in which the operations on every machine may overlap except for the machine with a given sequence of jobs. This relaxed problem is NP-hard in the ordinary sense, however it can be quickly solved via a decomposition into subset-sum problems. Both heuristic and branch-and-bound algorithm are proposed. Experimental results show that the heuristic is efficient for solving large-scaled problems, and the branch-and-bound algorithm performs well on small-scaled problems.Scope and purposeShop scheduling problems, widely used in the modeling of industrial production processes, are receiving an increasing amount of attention from researchers. To model practical production processes more closely, additional processing restrictions can be introduced, e.g., the resource constraints, the no-wait in process requirement, the precedence constraints, etc. This paper considers the total completion time open shop scheduling problem with a given sequence of jobs on one machine. This model belongs to a new class of shop scheduling problems under machine-dependent precedence constraints. This problem is NP-hard in the strong sense. A heuristic is proposed to efficiently solve large-scaled problems and a branch-and-bound algorithm is presented to optimally solve small-scaled problems. Computational experience is also reported.     

Scheduling deteriorating jobs on a single machine with release times

This paper investigates a single-machine deteriorating job scheduling problem with job release times where its objective is to minimize the makespan. The problem is known to be NP-hard. Therefore, a branch-and-bound algorithm incorporating with several dominance properties and lower bounds is proposed to derive the optimal solution for the problem. In addition, easy-implemented heuristic algorithms are also provided to obtain the near-optimal solution. The computational experiments indicate that the branch-and-bound algorithm can solve most of the medium-job-sized problems within a reasonable time, and the heuristic is quite accurate with an average error percentage of less than 0.3%.     

An exact algorithm for the budget-constrained multiple knapsack problem

This paper is concerned with a variant of the multiple knapsack problem (MKP), where knapsacks are available by paying certain ‘costs’, and we have a fixed budget to buy these knapsacks. Then, the problem is to determine the set of knapsacks to be purchased, as well as to allocate items into the accepted knapsacks in such a way as to maximize the net total profit. We call this the budget-constrained MKP and present a branch-and-bound algorithm to solve this problem to optimality. We employ the Lagrangian relaxation approach to obtain an upper bound. Together with the lower bound obtained by a greedy heuristic, we apply the pegging test to reduce the problem size. Next, in the branch-and-bound framework, we make use of the Lagrangian multipliers obtained above for pruning subproblems, and at each terminal subproblem, we solve MKP exactly by calling the MULKNAP code [D. Pisinger, An exact algorithm for large multiple knapsack problem, European J. Oper. Res. 114 (1999), pp. 528–541]. Thus, we were able to solve test problems with up to 160,000 items and 150 knapsacks within a few minutes in our computing environment. However, solving instances with relatively large number of knapsacks, when compared with the number of items, still remains hard. This is due to the weakness of MULKNAP to this type of problems, and our algorithm inherits this weakness as well.     

Minimizing makespan in three-machine flow shops with deteriorating jobs

In this paper, a three-machine permutation flow shop scheduling problem with time-dependent processing times is considered. By the time-dependent processing times we mean that the job's processing time is an increasing function of its starting time. The objective is to find a sequence that minimizes the makespan. This problem is well known to be NP-hard. Several dominance properties and a lower bound are derived to speed up the elimination process of a branch-and-bound algorithm. Moreover, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational experiments on randomly generated problems are conducted to evaluate the branch-and-bound algorithm and heuristic algorithm. Computational results show that the proposed heuristic algorithm M-NEH perform effectively and efficiently.     

A Best-first Branch-and-bound Algorithm for Orthogonal Rectangular Packing Problems

In this paper we discuss the problem of packing a set of small rectangles (pieces) in an enclosing final rectangle. We present first a best-first branch-and-bound exact algorithm and second a heuristic approach in order to solve exactly and approximately this problem. The performances of the proposed approaches are evaluated on several randomly generated problem instances. Computational results show that the proposed exact algorithm is able to solve small and medium problem instances within reasonable execution time. The derived heuristic performs very well in the sense that it produces high-quality solutions within small computational time.     

An efficient heuristic to dimension large-scale hybrid optoelectronic networks

This paper presents a new heuristic to solve efficiently the problem of dimensioning large-size hybrid optoelectronic networks with grooming. It is modeled as a large mixed integer program which cannot be solved to optimality in a reasonable amount of time for networks larger than 10 nodes. The heuristic is based on concepts borrowed from genetic algorithm, tabu search and simulated annealing. The definition of the populations and neighborhoods are discussed in depth along with the intensification and diversification procedures. An application of this heuristic to networks of up to 50 nodes has shown excellent results: The computational time is low and the average optimality gap is generally under 7%.     

A genetic algorithm approach to the multiple machine tool selection problem

A number of earlier researches have emphasized the on-the-job scheduling problems that occur with a single flexible machine. Two solutions to the problem have generally been considered; namely minimization of tool switches and minimization of tool switching instances. Methods used to solve the problems have included KTNS heuristic, dual-based relaxation heuristic, and non-LP-based branch-and-bound methods. However, scant literature has considered the case of job scheduling on multiple parallel machines which invokes another problem involving machine assignment. This paper addresses the problem of job scheduling and machine assignment on a flexible machining workstation (FMW) equipped with multiple parallel machines in a tool-sharing environment. Under these circumstances, the authors have attempted to model the problem with the objective of simultaneously minimizing both the number of tool switches and the number of tool switching instances. Furthermore, a set of realistic constraints has been included in the investigation. A novel genetic algorithm (GA) heuristic has been developed to solve the problem, and performance results show that GA is an appropriate solution.     

Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times

This paper considers a single-machine problem with the sum-of-processing time based learning effect and release times. The objective is to minimize the total weighted completion times. First, a branch-and-bound algorithm incorporating with several dominance properties and two lower bounds are developed for the optimal solution. Then a genetic heuristic-based algorithm is proposed for a near-optimal solution. Finally, a computational experiment is conducted to evaluate the performances of the proposed algorithms. The results show that the branch-and-bound algorithm can solve instances up to 15 jobs, and the average error percentage of the genetic heuristic algorithm is less than 0.105%.     

A virtual pegging approach to the max–min optimization of the bi-criteria knapsack problem

We are concerned with a variation of the knapsack problem, the bi-objective max–min knapsack problem (BKP), where the values of items differ under two possible scenarios. We have given a heuristic algorithm and an exact algorithm to solve this problem. In particular, we introduce a surrogate relaxation to derive upper and lower bounds very quickly, and apply the pegging test to reduce the size of BKP. We also exploit this relaxation to obtain an upper bound in the branch-and-bound algorithm to solve the reduced problem. To further reduce the problem size, we propose a ‘virtual pegging’ algorithm and solve BKP to optimality. As a result, for problems with up to 16,000 items, we obtain a very accurate approximate solution in less than a few seconds. Except for some instances, exact solutions can also be obtained in less than a few minutes on ordinary computers. However, the proposed algorithm is less effective for strongly correlated instances.     

Finding optimal hardware/software partitions

Most previous approaches to hardware/software partitioning considered heuristic solutions. In contrast, this paper presents an exact algorithm for the problem based on branch-and-bound. Several techniques are investigated to speed up the algorithm, including bounds based on linear programming, a custom inference engine to make the most out of the inferred information, advanced necessary conditions for partial solutions, and different heuristics to obtain high-quality initial solutions. It is demonstrated with empirical measurements that the resulting algorithm can solve highly complex partitioning problems in reasonable time. Moreover, it is about ten times faster than a previous exact algorithm based on integer linear programming. The presented methods can also be useful in other related optimization problems.     

Simulated annealing algorithm for solving the single machine early/tardy problem

Recently, several studies have been conducted regarding the application of the simulated annealing (SA) method to solve combinatorial optimization problems. Most of the previous reports have shown that SA has been used to obtain reasonable solutions that are better than some heuristic algorithms and in comparable CPU time. A single machine early/tardy problem is selected in this paper to demonstrate the usefulness of SA. Firstly, based on previous studies, this research uses the factorial experiment to analyse the factors that are critical to the efficiency of SA. Secondly, SA, tuned by the previous step, is compared with branch-and-bound and neighbourhood search methods by solving some test problems. The results show that SA is very sensitive to the cooling schedule, generation mechanism, acceptance criteria and stopping criteria. When SA is used to solve the single machine problem with n ≤ 15, it can converge to the optimal solution quickly. For the single machine problem where n ≥ 30, the branch-and-bound algorithm is not feasible while SA can provide a much better solution than the neighbourhood search method.     

A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs

We present a single-machine problem with the unequal release times under learning effect and deteriorating jobs when the objective is minimizing the makespan. In this study, we introduced a scheduling model with unequal release times in which both job deterioration and learning exist simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 30 jobs, and the average error percentage of the proposed heuristic is less than 0.16%.     

Deteriorating job scheduling to minimize the number of late jobs with setup times

Deteriorating jobs scheduling problems have been widely studied recently. However, research on scheduling problems with deteriorating jobs has rarely considered explicit setup times. With the current emphasis on customer service and meeting the promised delivery dates, we consider a single-machine scheduling problem to minimize the number of late jobs with deteriorating jobs and setup times in this paper. We derive some dominance properties, a lower bound, and an initial upper bound by using a heuristic algorithm to speed up the search process of the branch-and-bound algorithm. Computational experiments show that the algorithm can solve instances up to 1000 jobs in a reasonable amount of time.     

Scheduling algorithms to minimize the number of tardy jobs in two-stage hybrid flow shops

This paper considers a two-stage hybrid flow shop scheduling problem for the objective of minimizing the number of tardy jobs. Each job is processed through the two production stages in series, each of which has multiple identical parallel machines. The problem is to determine the allocation of jobs to the parallel machines as well as the sequence of the jobs assigned to each machine. To solve the problem, a branch and bound algorithm, which incorporates the methods to obtain the lower and upper bounds as well as the dominance properties to reduce the search space, is suggested that gives the optimal solutions. In addition, two-phase heuristic algorithms are suggested to obtain good solutions for large-size problems within a reasonable amount of computation time. To show the performances of the optimal and heuristic algorithms suggested in this paper, computational experiments are done on a number of randomly generated test problems, and the test results are reported.     

Minimizing total tardiness on a single machine with controllable processing times

The concept of time-cost trade-off is commonly considered in PERT/CPM, but it is seldom considered in the scheduling area. Such concept implies that the processing times of jobs are controllable by increasing or decreasing the available resources, such as manpower and equipment. In this paper, we focus on the single machine total tardiness problem with controllable processing times. First, a mixed-integer programming (MIP) model is formulated to find the optimal solution. Then, we propose both a linear programming model and a net benefit of compression (NBC) algorithm to obtain a set of optimal amounts of compression for a given sequence. To solve medium- to large-size problem instances, we develop a heuristic based on the NBC algorithm. To verify the proposed heuristic, the MIP model is used as a comparison for small-size problem instances, whereas for medium- to large-size instances the variable neighborhood search, a useful local search method, is employed. Computational results show that the proposed heuristic has a good performance.     

A combined parallel algorithm for solving the knapsack problem

Parallel implementations of a combined branch-and-bound algorithm for the knapsack problem with one constraint are considered. By the combined algorithm we mean an algorithm in which two methods of branching are implemented, the method based on an estimate of the upper bound and the method of one-sided branching based on the vector. An approach combining parallel implementations of the brunch-and-bound method and the heuristic search is proposed and implemented.     

Two-machine flow shop scheduling with linear decreasing job deterioration

In this paper, we consider a two-machine flow shop scheduling problem with deteriorating jobs. By a deteriorating job, we mean that the processing time is a decreasing function of its execution start time. A proportional linear decreasing deterioration function is assumed. The objective is to find a sequence that minimizes total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and some lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational results for randomly generated problem instances are presented, which show that the heuristic algorithm effectively and efficiently in obtaining near-optimal solutions.     

Branch-and-Bound-Based Local Search Heuristics for Train Timetabling on Single-Track Railway Network

The modified formulation and two branch-and-bound-based local search heuristic algorithms for train timetabling in single-track railway network in the planning application are proposed. The original local search heuristic is modified such that when a neighbor of a currently tested resolved conflict for improvement is evaluated, the depth-first search branch-and-bound algorithm is employed with two branching rules: least-lower-bound and least-delay-time. The detailed implementation of the proposed heuristic algorithms are described, including the neighborhood definitions of overtaking and crossing conflicts, the procedure to detect overtaking and crossing conflicts, and a recursive procedure for the depth-first search branch-and-bound algorithm. The proposed heuristic algorithms, the original heuristic, the equivalent manual solution method and the exact solution method are compared using a toy problem and four problems (26-train, 50-train, 76-train and 108-train) in the Thailand Southern line railway network, which consisted of 266 single-track segments, 15 double-track segments, 282 stations/sidings, and total distance of 1577 km. The proposed heuristic algorithm with the least-lower-bound branching rule outperforms the other heuristics in terms of the solution quality with up to 2.827 % improvement over the equivalent manual solution method and less than 8 % optimality gap. The proposed heuristic algorithms require longer time to terminate than the original heuristic. The proposed heuristic algorithm with the least-lower-bound branching rule converges faster than that with the least-delay-time branching rule in all test problems. Based on the empirical results, the proposed heuristic algorithms are solvable in polynomial time. Furthermore, the proposed heuristic algorithm with the least-lower-bound branching rule is enhanced by embedding a uniform sampling strategy, and it is found that the total CPU time can be saved by about 50 % with marginally worse solution quality.