•The Total Weighted Tardiness (TWT) is heuristically minimized by new decision rules.•The TWT heuristic is extended by our new rules to arbitrary processing times.•Schedules with up to 200 jobs and ...20 processing times are returned within 47 ms.
In this paper, we refine the ties within decision rules of the Total Weighted Tardiness (TWT) heuristic from Jaramillo and Erkoc (2017) applied by the authors to solving the preemptive single machine scheduling problem with arbitrary release and due dates, priority factors (weights), and equal processing times of a finite number of jobs. The TWT heuristic is intended to minimize the total weighted tardiness of schedules. Our refinements allow to extend equal processing times to arbitrary ones such that we are able to solve benchmark instances online with up to 200 jobs and 20 units of processing times within 47 ms and essentially decrease TWT of returned schedules. The time and space complexities of returned schedules outperform the state of the art for the cases of arbitrary release dates, weighted and unweighted total tardiness, with equal and arbitrary processing times.
•Total Weighted Tardiness heuristic is extended into a metaheuristic with 4 branches.•The metaheuristic is rendered to a single branch based on the problem type.•One of the 2 branches is executed ...depending on the job processing time.•The branches tend to become equally accurate as the problem size is increased.•Branches outperform exact solution approaches in scheduling more than 10 jobs.
This paper studies the scheduling of a finite set of jobs on a single machine. Jobs can be preempted. They are associated with respective release and due dates. In a more general case, each job has a priority weight. The objective is to minimize the total weighted tardiness. An optimal schedule providing the minimal total weighted tardiness can be found by our Boolean linear programming model, but it becomes computationally intractable as the problem size grows. Thus, we analyze the recently designed heuristic to minimize total weighted tardiness based on using the remaining available time and remaining processing time. It is a rapid online scheduling algorithm but the heuristic may return schedules whose tardiness deviates from an optimal value by 50% and more. We extend the heuristic into four branches with a purpose to improve it by excluding options of job selection uncertainty. Depending on the scheduling problem type, we render the metaheuristic to a single branch which is run after the main heuristic algorithm. This allows building schedules online. Our extensive computational study shows that our online metaheuristic returns high quality schedules.
Many real-world production and service environments can be modeled using the preemptive single machine scheduling problem with equal processing times, arbitrary release dates and weights (priorities) ...minimizing the total weighted completion time. For this problem we propose a Boolean Linear Programming model, two heuristics based on the model’s relaxation, and an exact Branch and Bound algorithm incorporating the model and heuristics. Our computational study involved more than one million problem instances with up to 350 jobs. Each generated instance has been solved to optimality within 31 min. That improves state-of-the art (at most 20 jobs in 60 min) by more than an order of magnitude. Our benchmark instances and optimal schedules are publicly available at https://data.mendeley.com/datasets/nrkx7467tf/1.
•A new Boolean Linear Programming model is coined.•Properties of optimal schedules are proven to justify the model.•Two high quality heuristics and an exact Branch and Bound algorithm are designed.•Exact algorithm substantially outperforms state-of-the-art algorithms.•Benchmark instances and optimal schedules are publicly available.
Submodular functions are powerful tools to model and solve either to optimality or approximately many operational research problems including problems defined on graphs. After reviewing some ...long-standing theoretical results about the structure of local and global maxima of submodular functions, Cherenin’s selection rules and his Dichotomy Algorithm, we revise the above mentioned theory and show that our revision is useful for creating new non-binary branching algorithms and finding either approximation solutions with guaranteed accuracy or exact ones.
The currently adopted notion of a tolerance in combinatorial optimization is defined referring to an arbitrarily chosen optimal solution, i.e., locally. In this paper we introduce global tolerances ...with respect to the set of all optimal solutions, and show that the assumption of nonembededdness of the set of feasible solutions in the provided relations between the extremal values of upper and lower global tolerances can be relaxed. The equality between globally and locally defined tolerances provides a new criterion for the multiplicity (uniqueness) of the set of optimal solutions to the problem under consideration.
Data Correcting Approaches in Combinatorial Optimization focuses on algorithmic applications of the well known polynomially solvable special cases of computationally intractable problems. The purpose ...of this text is to design practically efficient algorithms for solving wide classes of combinatorial optimization problems. Researches, students and engineers will benefit from new bounds and branching rules in development efficient branch-and-bound type computational algorithms. This book examines applications for solving the Traveling Salesman Problem and its variations, Maximum Weight Independent Set Problem, Different Classes of Allocation and Cluster Analysis as well as some classes of Scheduling Problems. Data Correcting Algorithms in Combinatorial Optimization introduces the data correcting approach to algorithms which provide an answer to the following questions: how to construct a bound to the original intractable problem and find which element of the corrected instance one should branch such that the total size of search tree will be minimized. The PC time needed for solving intractable problems will be adjusted with the requirements for solving real world problems.
•The job sequencing and tool switching problem (SSP) is approximated by the 2-TSP.•A dynamic Q-learning-based genetic algorithm (DQGA) is proposed.•The DQGA enables learning from the experience of ...selecting the order of operators.•The proposed method outperforms the state-of-the-art of models and algorithms.•The method can be used for scheduling problems with sequence-dependent setup time.
One of the well-known problems in single machine scheduling context is the Job Sequencing and Tool Switching Problem (SSP). The SSP is optimally sequencing a finite set of jobs and loading restricted subset of tools to a magazine with the aim of minimizing the total number of tool switches. It has been proved in the literature that the SSP can be reduced to the Job Sequencing Problem (JSeP). In the JSeP, the number of tool switches from the currently processed job to the next job depends on the sequencing of all predecessors. In this paper, the JSeP is modeled as a Traveling Salesman Problem of Second Order (2-TSP). We call the induced JSeP by 2-TSP as the Job Sequencing Problem of Second Order (2-JSeP) with a different objective function formulation from JSeP and prove that 2-JSeP is NP-hard. Then the Assignment Problem of Second Order (2-AP) and Karp-Steele patching heuristic are incorporated to solve 2-JSeP. The obtained solution, however, does not guarantee the optimal sequence and are used to seed a Dynamic Q-learning-based Genetic Algorithm (DQGA) to improve the solution quality. Q-learning, which is a kind of reinforcement learning method, is used to learn from the experience of selecting the order of mutation and crossover operators in each generation of the genetic algorithm. The computational results on 320 benchmark instances show that the proposed DQGA is comparable to the state-of-the-art methods in the literature. The DQGA even outperforms the existing methods for some instances, as could improve the reported “best-known solutions” in notably less time. Finally, through the statistical analysis, the performance of DQGA is compared with those of non-learning genetic algorithms.
The simple plant location problem is a well-studied problem in combinatorial optimization. It is one of deciding where to locate a set of plants so that a set of clients can be supplied by them at ...the minimum cost. This problem often appears as a subproblem in other combinatorial problems. Several branch and bound techniques have been developed to solve these problems. In this paper we present two techniques that enhance the performance of branch and bound algorithms. The new algorithms thus obtained are called branch and peg algorithms, where pegging refers to fixing values of variables at each subproblem in the branch and bound tree, and is distinct from variable fixing during the branching process. We present exhaustive computational experiments which show that the new algorithms generate less than 60% of the number of subproblems generated by branch and bound algorithms, and in certain cases require less than 10% of the execution times required by branch and bound algorithms.
Scope and purpose
Locational decision problems of choosing the location of facilities to satisfy the demand of a set of clients at minimum costs constitute a very important class of practical problems. The simple plant location problem is a subclass of such problems, in which the facilities are supposed to have infinite capacities. These problems are used to model, among others, bank account location problems and in cluster analysis (refer, for example, to Cornuejols et al. 1) and also, in recent times, to problems related to electronic business (refer to Fourer and Goux
2). Not only are these problems important in themselves, but they also appear as subproblems in a much wider class of combinatorial problems, for example in crew scheduling, vehicle despatching, assortment, etc. The simple plant location problem is
NP
-hard and there is much research on good algorithms for these problems. Effective solution techniques based on branch and bound algorithms have been suggested in the literature. In this paper we suggest techniques that substantially reduce the execution times of such algorithms. We think that these techniques can be used to enhance the performance of almost all the available solution algorithms for this problem. We hope that this paper will motivate research to apply the techniques suggested here to other problems.
Despite the long history of the cell formation problem (CF) and availability of dozens of approaches, very few of them explicitly optimize the objective of cell formation. These scarce approaches ...usually lead to intractable formulations that can be solved only heuristically for practical instances. In contrast, we show that CF can be explicitly modelled via the minimum multicut problem and solved to optimality in practice (for moderately sized instances). We consider several real-world constraints that can be included into the proposed formulations and provide experimental results with real manufacturing data.
PDF
