bound algorithm

In this paper, the single machine scheduling problem with linear deteriorating jobs under release times is considered where the objective is to minimize the number of tardy jobs. The problem is proved NP-hard according to the literature review. At first, a mathematical model is presented to the problem and a Branch and Bound algorithm with considering dominance rules and lower bounds is supposed to solve the problem optimally. Computational results are presented in four parts to evaluate the performance of the proposed algorithm and the effect of related parameters on the algorithm. According to the variance analysis test, it was found that the efficiency of the branch and bound algorithm is high so that it is able to solve the most problems with job size 30 within a reasonable time and the average percentage of entire fathomed nodes in all the problems is at least 85.61 percentage. It was also shown the problems with larger λ and smaller deterioration rates are difficult and the average solution time of the algorithm is high for them. On the other hand, if the due date of the jobs was big or small, the problem will be simple and the solution time is less than the problems with medium due dates.

Concurrently scheduling for two-stage production systems consist of a processing stage and an assembly stage causes to achieve the ideal result for these systems. This paper aims to propose a branch and bound (B&B) algorithm for the scheduling problem in a flexible job shop followed by an assembly stage. The objective function is the total completion time of products (makespan). Due to time consuming the classic B&B algorithms in solving optimization problems, two efficient lower bounds are developed to reduce the run time. Moreover, two search strategies the so-called the Best First Search (BFS) and the Depth-First Search (DFS) are introduced to enhance performance of the proposed algorithm. The variable neighborhood search (VNS) is applied to determine proper upper bound for solution of the problem. To more clarification, the problem is modeled as a mixed-integer linear programming (MIP) model with definition need parameters and decision variables. Since the problem is well known as NP-hard strongly, performance of the proposed algorithm is investigated in comparison to the exact solutions provided by the mathematical model for the small-sized instances. The evaluation results showed that the depth search strategy has performed better than the other one. This search strategy has could to enhance efficiency of the proposed algorithm, and has significantly reduced the solution time.

In this research, the operating room scheduling problem is studied. During recent years, this problem has attracted many researchers in an eort to reduce costs and raise the quality of health services. In this article, a surgery is divided to four steps and the required resources for each step are determined, where surgeons and operating rooms are the main critical resources. For this problem, a mixed integer programming model is developed, in which, assignment of patients to rooms and, also, the sequence of patient surgery, are determined, such that the bi-objective function, including additional work costs and idle time costs of surgeons, is minimized. This model is able to solve very small size problems in a reasonable time. Thus, a branch-and-bound algorithm has been developed to nd an optimal solution, in each node of which, a patient is assigned to a room. The sequence of operations for patients of a room and also for patients of a surgeon is established using parent-child relations of the search tree. Moreover, in order to prevent the enumeration of repetitive nodes or the extension of nodes that surely will not improve the best found solution, four properties are developed. This algorithm has been implemented in C++ programming language and a set of test problems are generated to evaluate its eciency and analyze the sensitivity of some parameters. Based upon presented results, the solution time is increased if each of the three following parameters is increased: Number of patients, number of surgeons or average number of possible rooms for each patient. In addition, it seems that if 20% is added to the total surgery time of each surgeon, this new time interval is proper to be considered as the working time interval, and longer intervals will not noticeably improve the quality of the optimal solution. It is shown in this paper that 0.25 is the best suitable coecient for the idle gaps of surgeons in the objective function.

Production capacity planning and scheduling are parts of decision process in supply chain of many manufacturing and service industries, which have important role in satisfying customer requirements and enhancing customer service level. Since these two processes performs in two different levels of supply chain (capacity planning in tactical level and scheduling in operational one), usually their decision are made independently. In such circumstances, the feasibility of capacity decisions in tactical level, when plan imports into the shop floor, is one of the critical challenges in this decision making approach. Hence in this paper, after formulating the capacity planning and two-machine scheduling problems integrately, an analytical solution approach will be presented. In order to minimize the maximum completion time of orders, concept of order pairs is defined and the optimal orders pairs are established based on the optimal solution of symmetric assignment problem. Afterwards, to determine the optimal sequence of order pairs, a branch and bound procedure is designed which is based on three proposed lower bounds, depth first and best first strategies. To improve the efficiency of algorithm, some mathematical properties are proved and some corresponding dominance rules are derived. Furthermore, to delineate the quantity of resource allocation to the operations, a neighborhood search algorithm is designed and improved based on some structural properties of problem.

In this paper, minimizing the number of tardy jobs in two-machine flowshop scheduling with non-simultaneous job entrance is discussed. It is proven that the complexity of the problem is NP_hard. Therefore, a heuristic algorithm is proposed to solve the large scale problems. Besides, an exact branch and bound algorithm with utilizing heuristic algorithm as upper bound proposed to achieve optimal solution. Computational results demonstrate that branch and bound method solves problems with 28 jobs in the set High and 20 jobs in the set Low in a reasonable time. Results show the capability of the proposed upper bound, lower bounds and dominance rules. Also, it is shown that the average ratio of optimal solution to the heuristic one with the objective ∑(1-Ui) is at most 1.11 which is smaller in contrast with other researches in the literature. This ratio proves efficacy of the proposed heuristic algorithm. Finally, according to efficiency of the presented approach, sample problems with large dimensions were solved and their results were displayed.