Search

We address the two-machine flow-shop scheduling problem with time delays in order to minimize the makespan, i.e., the maximum completion time. We present a comprehensive theoretical analysis of the different lower bounds of the state of the art and we elucidate dominance relationships between them. We then introduce an exact method based on a branch-and-bound scheme. This method includes a local search-based heuristic and three dominance rules. Finally, a computer simulation of the branch-and-bound method is given on a set of 480 instances. We point out the good performance of our branch-and-bound method that outperforms the state of the art exact method. Precisely, we manage to solve all the state of the art instances except one in a very short time. [ABSTRACT FROM AUTHOR]

This research considers a flexible flowshop sequence-dependent group scheduling problem with minimization of total completion time. A mixed integer linear mathematical model for the research problem is developed. Since the research problem is shown to be strongly NP-hard, a metaheuristic algorithm based on memetic algorithm (MA) is proposed. A lower bounding method based on the Branch and Price algorithm is also proposed to evaluate the quality of the MA. In order to evaluate the performance of the proposed algorithms, random test problems, ranging in size from small, medium, to large are generated and solved by the MA and the lower bounding method. The results show that the average percentage gap of the MA is 6.03 % compared to the result of the lower bounding method for randomly generated test problems. [ABSTRACT FROM AUTHOR]

This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose a new lower bound for the traveling tournament problem, and construct a randomized approximation algorithm yielding a feasible solution whose approximation ratio is less than 2+(9/4)/( n−1), where n is the number of teams. Additionally, we propose a deterministic approximation algorithm with the same approximation ratio using a derandomization technique. For the traveling tournament problem, the proposed algorithms are the first approximation algorithms with a constant approximation ratio, which is less than 2+3/4. [ABSTRACT FROM AUTHOR]

This paper addresses an identical parallel machine scheduling problem with job release dates and unavailability periods to minimize total weighted completion time. This problem is known to be NP-hard in the strong sense. We propose a new lower bound that can be computed in polynomial time. The test on more than 8 400 randomly generated instances shows a very significant improvement with respect to existing results for previously studied special cases: without unavailability constraints, unweighted version, or identical job release dates. For instance, the average improvement for the unweighted problem is as much as 20.43% for 2 machines, 53.03% for 7 machines and 66.70% for 15 machines. For some instances, the improvement can be even as much as 93%. [ABSTRACT FROM AUTHOR]

This work addresses the minimization of the makespan criterion for the flowshop problem with blocking. In this environment there are no buffers between successive machines, and therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. We propose a lower bound which exploits the occurrence of blocking. A branch-and-bound algorithm that uses this lower bound is described and its efficiency is evaluated on several problems. Results of computational experiments are reported. [ABSTRACT FROM AUTHOR]

We consider in this paper a two-machine flowshop scheduling problem in which the first machine processes jobs individually while the second machine processes jobs in batches. The forming of each batch on the second machine incurs a constant setup time. The objective is to minimize the makespan. This problem was previously shown to be NP-hard in the ordinary sense. In this paper, we first present a strong NP-hardness result of the problem. We also identify a polynomially solvable case with either anticipatory or non-anticipatory setups. We then establish a property that an optimal solution for the special case is a lower bound for the general problem. To obtain near-optimal solutions for the general problem, we devise some heuristics. The lower bound is used to evaluate the quality of the heuristic solutions. Results of computational experiments reveal that the heuristics produce solutions with small error ratios. They also suggest that the lower bound is close to the optimal solution. [ABSTRACT FROM AUTHOR]

In this paper, we investigate new lower bounds for the P| r j, q j| Cmax scheduling problem. A new bin packing based lower bound, as well as several new lifting procedures are derived for this strongly NP -hard problem. Extensive numerical experiments show that the proposed lower bounds consistently outperform the best existing ones. [ABSTRACT FROM AUTHOR]

We consider the problem of locating, on a network, n new facilities that interact with m existing facilities. In addition, pairs of new facilities interact. This problem, the multimedian location problem on a network, is known to be NP-hard. We give a new integer programming formulation of this problem, and show that its linear programming relaxation provides a lower bound that is superior to the bound provided by a previously published formulation. We also report results of computational testing with both formulations. [ABSTRACT FROM AUTHOR]

In this paper, we present a new lower bound for the open-shop problem. In shop problems, a classical lower bound LB is the maximum of job durations and machine loads. Contrary to the flow-shop and job-shop problems, the open-shop lacks lighter bounds. For the general open-shop problem OS, we propose an improved bound defined as the optimal makespan of a relaxed open-shop problem OSk. In OSk, the tasks of any job may be simultaneous, except for a selected job k. We prove the NP-hardness of OSk. However, for a fixed processing route of k, OSk boils down to subset-sum problems which can quickly be solved via dynamic programming. From this property, we define a branch-and-bound method for solving OSk which explores the possible processing routes of k. The resulting optimal makespan gives the desired bound for the initial problem OS. We evaluate the method on difficult instances created by a special random generator, in which all job durations and all machine loads are equal to a given constant. Our new lower bound is at least as good as LB and improves it typically by 4%, which is remarkable for a shop problem known for its rather small gaps between LB and the optimal makespan. Moreover, the computational times on a PC are quite small on average. As a by-product of the study, we determined and propose to the research community a set of very hard open-shop instances, for which the new bound improves LB by up to 30%. [ABSTRACT FROM AUTHOR]

The paper considers the three-machine open shop scheduling problem to minimize the makespan. It is assumed that each job consists of at most two operations, one of which is to be processed on the bottleneck machine, the same for all jobs. A new lower bound on the optimal makespan is derived, and a linear-time algorithm for finding an optimal non-preemptive schedule is presented. [ABSTRACT FROM AUTHOR]

The aim of this paper is to introduce Jackson's Pseudo Preemptive Schedule (JPPS) for them parallel and identical processor scheduling problem Pm/ri, qi/Cmax. JPPS generalizes Jackson's Preemptive Schedule (JPS) which was introduced for the one-processor sequencing problem 1/ri, qi/Cmax. JPS can be computed in O(n log n) time and plays a central role in solving NP-hard disjunctive scheduling problems such as the job shop problem. The make-span of JPPS can be computed in O(n log n + nm log m) time, and is a tight lower bound for the Pm/ri, qi/Cmax problem. So JPPS could also play a central role in solving the Resource Constrained Project Scheduling Problem. [ABSTRACT FROM AUTHOR]

We investigate the classical Gilmore–Lawler lower bound for the quadratic assignment problem. We provide evidence of the difficulty of improving the Gilmore–Lawler bound and develop new bounds by means of optimal reduction schemes. Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem. [ABSTRACT FROM AUTHOR]