A four-echelon supply chain network design with shortage: Mathematical modeling and solution methods

Often, companies deliberately fulfill demands with delay since they can benefit from reducing transportation and setup costs. This paper aims at designing a four-echelon supply chain structure including multiple suppliers, multiple producers, multiple distributors and multiple customers. The objectives are to minimize the total operating costs of all the supply chain elements and to maximize the reliability of the system. A number of transportation systems with different reliability rates are considered. The paper mathematically formulates the problem as a mixed integer linear programming model. In order to solve the large-sized instances of the problem, the paper proposes a novel heuristic algorithm called Comparative Particle Swarm Optimization. This algorithm employs a mechanism in order to compare the generated solutions and to prevent from generating worse solutions. The results of different numerical experiments endorse the effectiveness of the proposed heuristic.     

Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times

This research analyzes the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization of the identical parallel processing machines and is closer to real-world production systems. Each machine can accommodate and process several jobs simultaneously as a batch as long as the machine capacity is not exceeded. The batch processing time and the batch ready time are respectively equal to the largest processing time and the largest ready time among all the jobs in the batch. Motivated by the computational complexity and the practical relevance of the problem, we present several heuristics based on first-fit and best-fit earliest job ready time rules. We also present a mixed integer programming model for the problem and a lower bound to evaluate the quality of the heuristics. The small computational effort of deterministic heuristics, which is valuable in some practical applications, is also one of the reasons that motivates this study. The results show that the heuristic proposed in this paper has a superior performance compared to the heuristics based on ideas proposed in the literature.     

Hierarchical minimization of completion time variance and makespan in jobshops

This paper addresses the problem of minimizing makespan for a given set of n jobs to be processed on each of m machines in a static jobshop, subject to the minimum completion time variance (CTV). A lower bound on CTV is developed for the static jobshop problem. A backward scheduling approach is proposed using the observations on the development of lower bound for hierarchical minimization of CTV and makespan. A lower bound on makespan subject to minimum CTV is also presented for this problem. Finally, we present two simulated annealing heuristic approaches using the concepts of forward and backward scheduling. Their performances are compared against each other through the use of the lower bounds established in this work. The simulated annealing heuristic based on backward scheduling is shown to perform well by evaluating the developed heuristics on 82 jobshop problems taken from literature.     

Optimal multi-dimensional vector bin packing using simulated evolution

The use of the evolutionary heuristic simulated evolution for the optimization of the multi-dimensional vector bin packing problem, which is encountered in several industrial applications, is described. These applications range from production planning and steel fabrication to assignment of virtual machines (VMs) onto physical hosts at cloud-based data centers. The dimensions of VMs can include demands of CPU, memory, bandwidth, disk space etc. The generalized goodness functions that aid traversing the search space in an intelligent manner are designed to cater to the multidimensional nature of items (VMs). The efficiency of heuristics is tested by considering phase transition in the generation of difficult test cases. The quality of the heuristics is judged by determining how close the solution is to the estimated lower bound. A new implementation of a tighter lower bound is proposed. Experiments show that superior quality results are obtained by employing the proposed strategy.     

Robust supply chain design under uncertain demand in agile manufacturing

This paper considers a supply chain design problem for a new market opportunity with uncertain demand in an agile manufacturing setting. We consider the integrated optimization of logistics and production costs associated with the supply chain members. These problems routinely occur in a wide variety of industries including semiconductor manufacturing, multi-tier automotive supply chains, and consumer appliances to name a few. There are two types of decision variables: binary variables for selection of companies to form the supply chain and continuous variables associated with production planning. A scenario approach is used to handle the uncertainty of demand. The formulation is a robust optimization model with three components in the objective function: expected total costs, cost variability due to demand uncertainty, and expected penalty for demand unmet at the end of the planning horizon. The increase of computational time with the numbers of echelons and members per echelon necessitates a heuristic. A heuristic based on a k-shortest path algorithm is developed by using a surrogate distance to denote the effectiveness of each member in the supply chain. The heuristic can find an optimal solution very quickly in some small- and medium-size cases. For large problems, a “good” solution with a small gap relative to our lower bound is obtained in a short computational time.     

A multiple-vendor single-buyer integrated inventory model with a variable number of vendors

Supply chain management is concerned with the coordination of material and information flows in multi-stage production systems. A closer look at the literature reveals that previous research on the coordination of multi-stage production systems has predominantly focused on the sales side of the supply chain, whereas problems that arise on the supply side have often been neglected. This article closes this gap by studying the coordination of a supplier network in an integrated inventory model. Specifically, we consider a buyer sourcing a product from heterogeneous suppliers and tackle both the supplier selection and lot size decision with the objective to minimise total system costs. First, we provide mathematical formulations for the problem under study, and then suggest a two-stage solution procedure to derive a solution. Numerical studies indicate that our solution procedure reduces the total number of supplier combinations that have to be tested for optimality, and that it may support initiatives which aim on increasing the efficiency of the supply chain as a heuristic planning tool.     

Heuristic algorithms for two-machine flowshop with availability constraints

The majority of the scheduling studies carry a common assumption that machines are available all the time. However, machines may not always be available in the scheduling period due to breakdown or preventive maintenance. Taking preventive maintenance activity into consideration, we dealt with the two-machine flowshop scheduling problem with makespan objective. The preventive maintenance policy in this paper was dependent on the number of finished jobs. The integer programming model was proposed. We combined two recent constructive heuristics, HI algorithm and H algorithm, with Johnson’s algorithm, and named the combined heuristic H&J algorithm. We also developed a constructive heuristic, HD, with time complexities O(n²). Based on the difference in job processing times on two machines, both H&J and HD showed good performance, and the latter was slightly better. The HD algorithm was able to obtain the optimality in 98.88% of cases. We also employed the branch and bound (B&B) algorithm to obtain the optimum. With a good upper bound and a modified lower bound, the proposed B&B algorithm performed significantly effectively.     

An efficient variable partitioning approach for functional decomposition of circuits

Functional decomposition is a process of splitting a complex circuit into smaller sub-circuits. There exist two major strategies in decomposition, namely, serial and parallel decomposition. In serial decomposition the problem the complex function represented as a truth table with support set variables and partitioned into free and bout set variables. The minterms corresponding to the bound set variables are represented as an equivalent function called the predecessor function. Equivalent minterms of the bound set variables are assigned an output code. The assigned output codes and the free set variable minterms are represented as the successor function. Serial decomposition is further categorized into disjoint and non-disjoint decomposition, when the free and bound set variables are disjoint and non-disjoint respectively. This paper deals with the problem of determining the set of best free and bound variables (variable partitioning problem) for disjoint serial decomposition. Variable partitioning is the first step in decomposition process. An efficient variable partition algorithm is one that determines the set of all free and bound set variables that satisfy the decomposition theorem in minimal time and by exploring the search space effectively. This will allow the decomposition algorithm to determine the best variable partition of a function that results in smaller decomposed functions and with maximum number of do not cares in these functions. Classical approaches to determine the best free and bound set use exhaustive search methods. The time and memory requirements for such approaches are exponential or super exponential.A novel heuristic search approach is proposed to determine the set of good variable partitions in minimal time by minimally exploring the search space. There are two heuristics employed in the proposed search approach, (1) r-admissibility based heuristic or pruned breadth first search (PBFS) approach and (2) Information relation based heuristic or improved pruned breadth first search (IPBFS) approach. The r-admissibility based heuristic is based on r-partition characteristics of the free and bound set variables. The information relation and measure based heuristic is based on information relationship of free and bound set variables that are expressed as r-partition heuristics. The proposed variable partition search approach has been successfully implemented and test with MCNC and Espresso benchmarks and the results indicate that the time complexity is comparable to r-admissible heuristic algorithm and the quality of solution is comparable to exact variable partitioning algorithm. A comparison of PBFS and IPBFS heuristics for certain benchmarks are also discussed in this paper.     

供应链订单分配优化模型及其模拟退火算法

受4M1E(人、机、料、法、环)因素的随机波动影响,产品的制造过程通常是不完美的,从而产生不良产品.针对已有研究多忽略不良产品的特点,建立了更加符合实际需求的订单分配多目标混合整数规划模型,其优化目标为最小化交易成本、采购成本、不良产品数量、产品延迟交付数量,以及最大化供应商信誉评价.考虑到模型求解的复杂度,设计了一种模拟退火算法,并结合启发式规则避免了大量非法初始解与邻点解的出现.实验算例表明所建立的模型能够反映订单分配过程中的产品缺陷现象,其算法能够在允许的运算时间内获得稳定的满意解,并且随着算例规模的增大,其计算时间与优化结果均优于LINGO软件.     

Evaluating flexibility on order quantity and delivery lead time for a supply chain system

Most of the previous literature on production flexibility is centred on the flexibility of manufacturing systems. However, the manufacturing system is just one of several key components of a supply chain. A supply chain is a network involving all of the activities within individual organisations that link material suppliers, manufacturing factories, distributors, warehouses, retailers and customers. Research into the flexibility of a supply chain therefore extends from the intra-organisational flexibilities to the inter-organisational flexibilities. This article provides a study of examining two aspects of supply chain flexibility: order quantity flexibility and lead time flexibility, which have been clarified as the two most common changes which occur in supply chains. Order quantity flexibility refers to the ability to provide proper order quantity for customer needs. Lead time flexibility allows customers to set the order due date depending on their needs. A simulation model is built to evaluate the performance on different flexibility levels of a supply chain. The experimental results provide interesting insights and can be applied in selecting suppliers with order quantity flexibility and delivery lead time flexibility.     

The two-stage assembly scheduling problem to minimize total completion time with setup times

We address the two-stage assembly scheduling problem where there are m machines at the first stage and an assembly machine at the second stage. The objective is to schedule the available n jobs so that total completion time of all n jobs is minimized. Setup times are treated as separate from processing times. This problem is NP-hard, and therefore we present a dominance relation and propose three heuristics. The heuristics are evaluated based on randomly generated data. One of the proposed heuristics is known to be the best heuristic for the case of zero setup times while another heuristic is known to perform well for such problems. A new version of the latter heuristic, which utilizes the dominance relation, is proposed and shown to perform much better than the other two heuristics.     

On look-ahead heuristics in disjunctive logic programming

Disjunctive logic programming (DLP), also called answer set programming (ASP), is a convenient programming paradigm which allows for solving problems in a simple and highly declarative way. The language of DLP is very expressive and able to represent even problems of high complexity (every problem in the complexity class ${{\Sigma}_{2}^{P}} = {\rm NP}^{{\rm NP}}$ ). During the last decade, efficient systems supporting DLP have become available. Virtually all of these systems internally rely on variants of the Davis–Putnam procedure (for deciding propositional satisfiability [SAT]), combined with a suitable model checker. The heuristic for the selection of the branching literal (i.e., the criterion determining the literal to be assumed true at a given stage of the computation) dramatically affects the performance of a DLP system. While heuristics for SAT have received a fair deal of research, only little work on heuristics for DLP has been done so far. In this paper, we design, implement, optimize, and experiment with a number of heuristics for DLP. We focus on different look-ahead heuristics, also called “dynamic heuristics” (the DLP equivalent of unit propagation [UP] heuristics for SAT). These are branching rules where the heuristic value of a literal Q depends on the result of taking Q true and computing its consequences. We motivate and formally define a number of look-ahead heuristics for DLP programs. Furthermore, since look-ahead heuristics are computationally expensive, we design two techniques for optimizing the burden of their computation. We implement all the proposed heuristics and optimization techniques in DLV—the state-of-the-art implementation of disjunctive logic programming, and we carry out experiments, thoroughly comparing the heuristics and optimization techniques on a large number of instances of well-known benchmark problems. The results of these experiments are very interesting, showing that the proposed techniques significantly improve the performance of the DLV system.     

Developing usability heuristics with PROMETHEUS: A case study in virtual learning environments

Heuristic evaluation is one of the most widely-used methods for evaluating the usability of a software product. Proposed in 1990 by Nielsen and Molich, it consists in having a small group of evaluators performing a systematic revision of a system under a set of guiding principles known as usability heuristics. Although Nielsen’s 10 usability heuristics are used as the de facto standard in the process of heuristic evaluation, recent research has provided evidence not only for the need of custom domain specific heuristics, but also for the development of methodological processes to create such sets of heuristics. In this work we apply the PROMETHEUS methodology, recently proposed by the authors, to develop the VLEs heuristics: a novel set of usability heuristics for the domain of virtual learning environments. In addition to the development of these heuristics, our research serves as further empirical validation of PROMETHEUS. To validate our results we performed an heuristic evaluation using both VLEs and Nielsen’s heuristics. Our design explicitly controls the effect of evaluator variability by using a large number of evaluators. Indeed, for both sets of heuristics the evaluation was performed independently by 7 groups of 5 evaluators each. That is, there were 70 evaluators in total, 35 using VLEs and 35 using Nielsen’s heuristics. In addition, we perform rigorous statistical analyses to establish the validity of the novel VLEs heuristics. The results show that VLEs perform better than Nielsen’s heuristics, finding more problems, which are also more relevant to the domain, as well as satisfying other quantitative and qualitative criteria. Finally, in contrast to evaluators using Nielsen’s heuristics, evaluators using VLEs heuristics reported greater satisfaction regarding utility, clarity, ease of use, and need of additional elements.     

Location and allocation decisions for multi-echelon supply chain network – A multi-objective evolutionary approach

This paper aims at multi-objective optimization of single-product for four-echelon supply chain architecture consisting of suppliers, production plants, distribution centers (DCs) and customer zones (CZs). The key design decisions considered are: the number and location of plants in the system, the flow of raw materials from suppliers to plants, the quantity of products to be shipped from plants to DCs, from DCs to CZs so as to minimize the combined facility location and shipment costs subject to a requirement that maximum customer demands be met. To optimize these two objectives simultaneously, four-echelon network model is mathematically represented considering the associated constraints, capacity, production and shipment costs and solved using swarm intelligence based Multi-objective Hybrid Particle Swarm Optimization (MOHPSO) algorithm. This evolutionary based algorithm incorporates non-dominated sorting algorithm into particle swarm optimization so as to allow this heuristic to optimize two objective functions simultaneously. This can be used as decision support system for location of facilities, allocation of demand points and monitoring of material flow for four-echelon supply chain network.     

A hybrid Lagrangean heuristic with GRASP and path-relinking for set k-covering

The set multicovering or set k-covering problem is an extension of the classical set covering problem, in which each object is required to be covered at least k times. The problem finds applications in the design of communication networks and in computational biology. We describe a GRASP with path-relinking heuristic for the set k-covering problem, as well as the template of a family of Lagrangean heuristics. The hybrid GRASP Lagrangean heuristic employs the GRASP with path-relinking heuristic using modified costs to obtain approximate solutions for the original problem. Computational experiments carried out on 135 test instances show experimentally that the Lagrangean heuristics performed consistently better than GRASP as well as GRASP with path-relinking. By properly tuning the parameters of the GRASP Lagrangean heuristic, it is possible to obtain a good trade-off between solution quality and running times. Furthermore, the GRASP Lagrangean heuristic makes better use of the dual information provided by subgradient optimization and is able to discover better solutions and to escape from locally optimal solutions even after the stabilization of the lower bounds, when other Lagrangean strategies fail to find new improving solutions.     

Using MDA for integration of heterogeneous components in software supply chains

Software product lines are increasingly built using components from specialized suppliers. A company that is in the middle of a supply chain has to integrate components from its suppliers and offer (partially configured) products to its customers. To satisfy both the variability required by each customer and the variability required to satisfy different customers’ needs, it may be necessary for such a company to use components from different suppliers, partly offering the same feature set. This leads to a product line with alternative components, possibly using different mechanisms for interfacing, binding and variability, which commonly occurs in embedded software development.     

Heuristics for planning with penalties and rewards formulated in logic and computed through circuits

The automatic derivation of heuristic functions for guiding the search for plans is a fundamental technique in planning. The type of heuristics that have been considered so far, however, deal only with simple planning models where costs are associated with actions but not with states. In this work we address this limitation by formulating a more expressive planning model and a corresponding heuristic where preferences in the form of penalties and rewards are associated with fluents as well. The heuristic, that is a generalization of the well-known delete-relaxation heuristic, is admissible, informative, but intractable. Exploiting a correspondence between heuristics and preferred models, and a property of formulas compiled in d-DNNF, we show however that if a suitable relaxation of the domain, expressed as the strong completion of a logic program with no time indices or horizon is compiled into d-DNNF, the heuristic can be computed for any search state in time that is linear in the size of the compiled representation. This representation defines an evaluation network or circuit that maps states into heuristic values in linear-time. While this circuit may have exponential size in the worst case, as for OBDDs, this is not necessarily so. We report empirical results, discuss the application of the framework in settings where there are no goals but just preferences, and illustrate the versatility of the account by developing a new heuristic that overcomes limitations of delete-based relaxations through the use of valid but implicit plan constraints. In particular, for the Traveling Salesman Problem, the new heuristic captures the exact cost while the delete-relaxation heuristic, which is also exponential in the worst case, captures only the Minimum Spanning Tree lower bound.     

Downward pattern refinement for timed automata

Directed model checking is a well-established approach for detecting error states in concurrent systems. A popular variant to find shortest error traces is to apply the A\(^*\) search algorithm with distance heuristics that never overestimate the real error distance. An important class of such distance heuristics is the class of pattern database heuristics. Pattern database heuristics are built on abstractions of the system under consideration. In this paper, we propose downward pattern refinement, a systematic approach for the construction of pattern database heuristics for concurrent systems of timed automata. First, we propose a general framework for pattern databases in the context of timed automata and show that desirable theoretical properties hold for the resulting pattern database. Afterward, we formally define a concept to measure the accuracy of abstractions. Based on this concept, we propose an algorithm for computing succinct abstractions that are still accurate to produce informed pattern databases. We evaluate our approach on large and complex industrial problems. The experiments show the practical potential of the resulting pattern database heuristic.     

A revisit of fast greedy heuristics for mapping a class of independent tasks onto heterogeneous computing systems

Mixed-machine heterogeneous computing (HC) environments utilize a distributed suite of different high-performance machines, interconnected with high-speed links, to perform groups of computing-intensive applications that have diverse computational requirements and constraints. The problem of optimally mapping a class of independent tasks onto the machines of an HC environment has been proved, in general, to be NP-complete, thus requiring the development of heuristic techniques for practical usage. If the mapping has real-time requirements such that the mapping process is performed during task execution, fast greedy heuristics must be adopted. This paper investigates fast greedy heuristics for this problem and identifies the importance of the concept of task consistency in designing this mapping heuristic. We further propose task priority graph based fast greedy heuristics, which consider the factors of both task consistency and machine consistency (the same concept of consistency as in previous studies). A collection of 20 greedy heuristics, including 17 newly proposed ones, are implemented, analyzed, and systematically compared within a uniform model of task execution time. This model is implemented by the coefficient-of-variation based method. The experimental results illuminate the circumstances when a specific greedy heuristic would outperform the other 19 greedy heuristics.     

On a class of branching problems in broadcasting and distribution

We introduce the following network optimization problem: given a directed graph with a cost function on the arcs, demands at the nodes, and a single source s, find the minimum cost connected subgraph from s such that its total demand is no less than lower bound D. We describe applications of this problem to disaster relief and media broadcasting, and show that it generalizes several well-known models including the knapsack problem, the partially ordered knapsack problem, the minimum branching problem, and certain scheduling problems. We prove that our problem is strongly NP-complete and give an integer programming formulation. We also provide five heuristic approaches, illustrate them with a numerical example, and provide a computational study on both small and large sized, randomly generated problems. The heuristics run efficiently on the tested problems and provide solutions that, on average, are fairly close to optimal.