Fuzzy project scheduling problem and its hybrid intelligent algorithm

Project scheduling problem is to determine the schedule of allocating resources so as to balance the total cost and the completion time. This paper considers a type of project scheduling problem with fuzzy activity duration times. According to some management goals, three types of fuzzy models are built to solve the project scheduling problem. Moreover, the technique of fuzzy simulation and genetic algorithm are integrated to design a hybrid intelligent algorithm to solve the fuzzy models. Finally, some numerical examples are given to illustrate the effectiveness of the algorithm.     

Fuzzy minimum weight edge covering problem

Minimum weight edge covering problem, known as a classic problem in graph theory, is employed in many scientific and engineering applications. In the applications, the weight may denote cost, time, or opponent’s payoff, which can be vague in practice. This paper considers the edge covering problem under fuzzy environment, and formulates three models which are expected minimum weight edge cover model, α-minimum weight edge cover model, and the most minimum weight edge cover model. As an extension for the models, we respectively introduce the crisp equivalent of each model in the case that the weights are independent trapezoidal fuzzy variables. Due to the complexity of the problem, a hybrid intelligent algorithm is employed to solve the models, which can deal with the problem with any type of fuzzy weights. At last, some numerical experiments are given to show the application of the models and the robustness of the algorithm.     

Solving project scheduling problem with the philosophy of fuzzy random programming

Project scheduling problem is to determine the schedule of allocating resources to achieve the trade-off between the project cost and the completion time. In real projects, the trade-off between the project cost and the completion time, and the uncertainty of the environment are both considerable aspects for managers. Due to the complex external environment, this paper considers project scheduling problem with coexisted uncertainty of randomness and fuzziness, in which the philosophy of fuzzy random programming is introduced. Based on different ranking criteria of fuzzy random variables, three types of fuzzy random models are built. Besides, a searching approach by integrating fuzzy random simulations and genetic algorithm is designed for searching the optimal schedules. The goal of the paper is to provide a new method for solving project scheduling problem in hybrid uncertain environments.     

基于多阶段模糊规模效应量化的TMC模式下供应链调度优化研究

旅游大规模定制(Tourism Mass Customization, TMC)模式实施的关键是通过对旅游供应链的调度优化处理旅游活动的“规模效应”与游客“个性化需求”之间的矛盾问题。运用经济学及模糊数学的理论方法分析并实现了TMC模式下存在的多阶段模糊规模效应量化处理。构建了引入规模效应量化的服务成本最小化、引入模糊时间窗的顾客满意度最大化及供应链协同度最大化为优化目标的TMC模式下多目标供应链调度优化模型。最后,通过蚁群算法实现TMC模式下多调度优化目标的求解并对优化效果进行对比研究。研究结果表明,TMC模式下供应链调度中旅游活动存在多阶段模糊规模效应并且可以量化处理;TMC模式中的规模效应具有合理的区间范围,旅游企业应注重规模效应与其他目标的均衡;蚂蚁算法在求解TMC模式下多目标优化问题方面不仅收敛速度快,而且通过对多调度目标优化效果的对比检验表明,性能稳健优良。     

A graph-oriented approach for the minimization of the number of late jobs for the parallel machines scheduling problem

An O(n²) algorithm is presented for the n jobs m parallel machines problem with identical processing times. Due dates for each job are given and the objective is the minimization of the number of late jobs. Preemption is permitted. The problem can be formulated as a maximum flow network model. The optimality proof as well as other properties and a complete example are given.     

云制造平台加工能力分享调度优化研究

云制造平台加工能力分享的调度优化是云制造模式的核心运营问题。为提高云制造平台对参与能力分享企业资源的利用率,解决实际云制造需求环境下企业级制造资源调度问题,达到云制造平台动态实时的要求,以最小化工期和成本为目标函数,构建了基于平台并面向分享的云加工能力调度模型。为快速求解多个云任务订单的最优调度序列,引入任务简易编码和随机权重,设计了改进的二阶粒子群算法,并提出可分享加工能力时间窗的更新策略。最后,通过算例验证云制造平台加工能力调度机制的可行性和有效性。     

Minimizing shifts for personnel task scheduling problems: A three-phase algorithm

The personnel task scheduling problem is a subject of commercial interest which has been investigated since the 1950s. This paper proposes an effective and efficient three-phase algorithm for solving the shift minimization personnel task scheduling problem (SMPTSP). To illustrate the increased efficacy of the proposed algorithm over an existing algorithm, computational experiments are performed on a test problem set with characteristics motivated by employee scheduling applications. Experimental results show that the proposed algorithm outperforms the existing algorithm in terms of providing optimal solutions, improving upon most of the best-known solutions and revealing high-quality feasible solutions for those unsolved test instances in the literature.     

A fuzzy goal programming approach to integrated loading and scheduling of a batch processing machine

This paper concerns a real-life problem of loading and scheduling a batch-processing machine. The integrated loading and scheduling problem is stated as a multicriteria optimization problem where different types of objectives are included: (1) short-term objectives of relevance to the shop floor, such as throughput maximization and work-in-process inventory minimization, and (2) long-term objectives such as balancing of end product inventory levels and meeting financial targets imposed by the higher production planning level. Two types of uncertainty are considered: (1) uncertainty inherent in loading and scheduling objective targets (goals) such as the allocated budget and end product demand, and (2) uncertainty in importance relations among the objectives. These two types of uncertainty are modelled using fuzzy sets and fuzzy relations, respectively. A fuzzy goal programming model and the corresponding method are developed which handle both fuzzy and crisp goals and fuzzy importance relations among the goals. Numerical examples are given to illustrate the effectiveness of the developed model.     

Simultaneously scheduling multiple turns for steel color-coating production

This paper investigates a large-scale scheduling problem in the iron and steel industry, called color-coating production scheduling (CCPS). The problem is to generate multiple production turns for the galvanized coils that dynamically arrive from upstream lines within a given scheduling horizon, and at the same time determine the sequence of these turns so that the productivity and product quality are maximized while the production cost and the number of generated turns are minimized. We formulate this problem as a mixed integer nonlinear program and propose a tabu search heuristic to obtain satisfactory solutions. Results on real production instances show that the presented model and heuristic are more effective and efficient with comparison to manual scheduling. A practical scheduling system for CCPS combining the model and heuristic has been developed and successfully implemented in a major iron and steel enterprise in China.     

On minimum power connectivity problems

Given a (directed or undirected) graph with edge costs, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of its nodes. Motivated by applications for wireless networks, we present polynomial and improved approximation algorithms, as well as inapproximability results, for some classic network design problems under the power minimization criteria. Our main result is for the problem of finding a min-power subgraph that contains k internally-disjoint vs-paths from every node v to a given node s: we give a polynomial algorithm for directed graphs and a logarithmic approximation algorithm for undirected graphs. In contrast, we will show that the corresponding edge-connectivity problems are unlikely to admit even a polylogarithmic approximation.     

Capacitated location allocation problem with stochastic location and fuzzy demand: A hybrid algorithm

In this article, a capacitated location allocation problem is considered in which the demands and the locations of the customers are uncertain. The demands are assumed fuzzy, the locations follow a normal probability distribution, and the distances between the locations and the customers are taken Euclidean and squared Euclidean. The fuzzy expected cost programming, the fuzzy β-cost minimization model, and the credibility maximization model are three types of fuzzy programming that are developed to model the problem. Moreover, two closed-form Euclidean and squared Euclidean expressions are used to evaluate the expected distance between customers and facilities. In order to solve the problem at hand, a hybrid intelligent algorithm is applied in which the simplex algorithm, fuzzy simulation, and a modified genetic algorithm are integrated. Finally, in order to illustrate the efficiency of the proposed hybrid algorithm, some numerical examples are presented.     

Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots

This paper addresses cyclic scheduling of a no-wait robotic cell with multiple robots. In contrast to many previous studies, we consider r-degree cyclic (r > 1) schedules, in which r identical parts with constant processing times enter and leave the cell in each cycle. We propose an algorithm to find the minimal number of robots for all feasible r-degree cycle times for a given r (r > 1). Consequently, the optimal r-degree cycle time for any given number of robots for this given r can be obtained with the algorithm. To develop the algorithm, we first show that if the entering times of r parts, relative to the start of a cycle, and the cycle time are fixed, minimizing the number of robots for the corresponding r-degree schedule can be transformed into an assignment problem. We then demonstrate that the cost matrix for the assignment problem changes only at some special values of the cycle time and the part entering times, and identify all special values for them. We solve our problem by enumerating all possible cost matrices for the assignment problem, which is subsequently accomplished by enumerating intervals for the cycle time and linear functions of the part entering times due to the identification of the special values. The algorithm developed is shown to be polynomial in the number of machines for a fixed r, but exponential if r is arbitrary.     

Scheduling with controllable release dates and processing times: Makespan minimization

The paper deals with the single-machine scheduling problem in which job processing times as well as release dates are controllable parameters and they may vary within given intervals. While all release dates have the same boundary values, the processing time intervals are arbitrary. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amount. The objective is to minimize the makespan together with the total compression cost. We construct a reduction to the assignment problem for the case of equal release date compression costs and develop an O(n²) algorithm for the case of equal release date compression costs and equal processing time compression costs. For the bicriteria version of the latter problem with agreeable processing times, we suggest an O(n²) algorithm that constructs the breakpoints of the efficient frontier.     

Efficient algorithms for a family of matroid intersection problems

Consider a matroid where each element has a real-valued cost and a color, red or green; a base is sought that contains q red elements and has smallest possible cost. An algorithm for the problem on general matroids is presented, along with a number of variations. Its efficiency is demonstrated by implementations on specific matroids. In all cases but one, the running time matches the best-known algorithm for the problem without the red element constraint: On graphic matroids, a smallest spanning tree with q red edges can be found in time O(n log n) more than what is needed to find a minimum spanning tree. A special case is finding a smallest spanning tree with a degree constraint; here the time is only O(m + n) more than that needed to find one minimum spanning tree. On transversal and matching matroids, the time is the same as the best-known algorithms for a minimum cost base. This also holds for transversal matroids for convex graphs, which model a scheduling problem on unit-length jobs with release times and deadlines. On partition matroids, a linear-time algorithm is presented. Finally an algorithm related to our general approach finds a smallest spanning tree on a directed graph, where the given root has a degree constraint. Again the time matches the best-known algorithm for the problem without the red element (i.e., degree) constraint.     

A contribution to the stochastic flow shop scheduling problem

This paper deals with performance evaluation and scheduling problems in m machine stochastic flow shop with unlimited buffers. The processing time of each job on each machine is a random variable exponentially distributed with a known rate. We consider permutation flow shop. The objective is to find a job schedule which minimizes the expected makespan. A classification of works about stochastic flow shop with random processing times is first given. In order to solve the performance evaluation problem, we propose a recursive algorithm based on a Markov chain to compute the expected makespan and a discrete event simulation model to evaluate the expected makespan. The recursive algorithm is a generalization of a method proposed in the literature for the two machine flow shop problem to the m machine flow shop problem with unlimited buffers. In deterministic context, heuristics (like CDS [Management Science 16 (10) (1970) B630] and Rapid Access [Management Science 23 (11) (1977) 1174]) and metaheuristics (like simulated annealing) provide good results. We propose to adapt and to test this kind of methods for the stochastic scheduling problem. Combinations between heuristics or metaheuristics and the performance evaluation models are proposed. One of the objectives of this paper is to compare the methods together. Our methods are tested on problems from the OR-Library and give good results: for the two machine problems, we obtain the optimal solution and for the m machine problems, the methods are mutually validated.     

Interactive decision making for uncertain minimum spanning tree problems with total importance based on a risk-management approach

This paper deals with a minimum spanning tree problem where each edge cost includes uncertainty and importance measure. In risk management to avoid adverse impacts derived from uncertainty, a d-confidence interval for the total cost derived from robustness is introduced. Then, by maximizing the considerable region as well as minimizing the cost-importance ratio, a biobjective minimum spanning tree problem is proposed. Furthermore, in order to satisfy the objects of the decision maker and to solve the proposed model in mathematical programming, fuzzy goals for the objects are introduced as satisfaction functions, and an exact solution algorithm is developed using interactive decision making and deterministic equivalent transformations. Numerical examples are provided to compare our proposed model with some previous models.     

Approximate solution of the <Emphasis Type="Italic">p</Emphasis>-median minimization problem

A version of the facility location problem (the well-known p-median minimization problem) and its generalization—the problem of minimizing a supermodular set function—is studied. These problems are NP-hard, and they are approximately solved by a gradient algorithm that is a discrete analog of the steepest descent algorithm. A priori bounds on the worst-case behavior of the gradient algorithm for the problems under consideration are obtained. As a consequence, a bound on the performance guarantee of the gradient algorithm for the p-median minimization problem in terms of the production and transportation cost matrix is obtained.     

Charging scheduling problem of an M-to-N electric vehicle charger

This study investigates a real case of charging scheduling of an electric vehicle charger with multiple ports called M-to-N charger. The charger is designed for a multi-unit dwelling facility and can charge N electric vehicles simultaneously despite the supplied charging capacity being limited to only M electric vehicles. The electric vehicles arrive at the charger randomly and stay for their desired length of time, during which they must be charged as much as possible with minimum electric cost. The scheduling problem considers four objectives: maximizing the total charging amount, minimizing the total charging cost, minimizing the charging completion time, and maximizing the charging balance among the electric vehicles. A mixed-integer linear programming model and a relaxation-based heuristic algorithm are developed. Computational experiment results show that the proposed heuristic algorithm can generate schedules within 8 s for this case study by using an open-source linear programming solver. Compared with the mixed-integer programming algorithm, the proposed heuristic algorithm can provide solutions with less than 7% charging amount gap and 4% price gap. The proposed heuristic algorithm is successfully implemented in a real M-to-N charger.     

Optimal production inventory policy for defective items with fuzzy time period

In this paper, an optimal production inventory model with fuzzy time period and fuzzy inventory costs for defective items is formulated and solved under fuzzy space constraint. Here, the rate of production is assumed to be a function of time and considered as a control variable. Also the demand is linearly stock dependent. The defective rate is taken as random, the inventory holding cost and production cost are imprecise. The fuzzy parameters are converted to crisp ones using credibility measure theory. The different items have the different imprecise time periods and the minimization of cost for each item leads to a multi-objective optimization problem. The model is under the single management house and desired inventory level and product cost for each item are prescribed. The multi-objective problem is reduced to a single objective problem using Global Criteria Method (GCM) and solved with the help of Fuzzy Riemann Integral (FRI) method, Kuhn–Tucker condition and Generalised Reduced Gradient (GRG) technique. In optimum results including production functions and corresponding optimum costs for the different models are obtained and then are presented in tabular forms.     

An interval approach based on expectation optimization for fuzzy random bilevel linear programming problems

This paper considers a class of bilevel linear programming problems in which the coefficients of both objective functions are fuzzy random variables. The main idea of this paper is to introduce the Pareto optimal solution in a multi-objective bilevel programming problem as a solution for a fuzzy random bilevel programming problem. To this end, a stochastic interval bilevel linear programming problem is first introduced in terms of α-cuts of fuzzy random variables. On the basis of an order relation of interval numbers and the expectation optimization model, the stochastic interval bilevel linear programming problem can be transformed into a multi-objective bilevel programming problem which is solved by means of weighted linear combination technique. In order to compare different optimal solutions depending on different cuts, two criterions are given to provide the preferable optimal solutions for the upper and lower level decision makers respectively. Finally, a production planning problem is given to demonstrate the feasibility of the proposed approach.