A meta-heuristic algorithm for the fuzzy assembly line balancing type-E problem

Consideration is given to a single-model assembly line balancing problem with fuzzy task processing times. The problem referred to herein as f-SALBP-E consists of finding a combination of the number of workstations and the cycle time as well as a respective line balance such that the efficiency of the line is maximized. f-SALBP-E is an extension of the classical SALBP-E under fuzziness. First, a formulation of the problem is given with the tasks processing times presented by triangular fuzzy membership functions. Then, since the problem is known to be NP-hard, a meta-heuristic based on a Genetic Algorithm (GA) is developed for its solution. The performance of the proposed solution approach is studied and discussed over multiple benchmarks test problems taken from the open literature. The results demonstrate very satisfactory performance for the developed approach in terms of both solution time and quality.     

Two parameter tuned multi-objective evolutionary algorithms for a bi-objective vendor managed inventory model with trapezoidal fuzzy demand

This paper presents a bi-objective vendor managed inventory (BOVMI) model for a supply chain problem with a single vendor and multiple retailers, in which the demand is fuzzy and the vendor manages the retailers’ inventory in a central warehouse. The vendor confronts two constraints: number of orders and available budget. In this model, the fuzzy demand is formulated using trapezoidal fuzzy number (TrFN) where the centroid defuzzification method is employed to defuzzify fuzzy output functions. Minimizing both the total inventory cost and the warehouse space are the two objectives of the model. Since the proposed model is formulated into a bi-objective integer nonlinear programming (INLP) problem, the multi-objective evolutionary algorithm (MOEA) of non-dominated sorting genetic algorithm-II (NSGA-II) is developed to find Pareto front solutions. Besides, since there is no benchmark available in the literature to validate the solutions obtained, another MOEA, namely the non-dominated ranking genetic algorithms (NRGA), is developed to solve the problem as well. To improve the performances of both algorithms, their parameters are calibrated using the Taguchi method. Finally, conclusions are made and future research works are recommended.     

Fuzzy activity time-based model predictive control of open-station assembly lines

The sequencing and line balancing of manual mixed-model assembly lines are challenging tasks due to the complexity and uncertainty of operator activities. The control of cycle time and the sequencing of production can mitigate the losses due to non-optimal line balancing in the case of open-station production where the operators can work ahead of schedule and try to reduce their backlog. The objective of this paper is to provide a cycle time control algorithm that can improve the efficiency of assembly lines in such situations based on a specially mixed sequencing strategy. To handle the uncertainty of activity times, a fuzzy model-based solution has been developed. As the production process is modular, the fuzzy sets represent the uncertainty of the elementary activity times related to the processing of the modules. The optimistic and pessimistic estimates of the completion of activity times extracted from the fuzzy model are incorporated into a model predictive control algorithm to ensure the constrained optimization of the cycle time. The applicability of the proposed method is demonstrated based on a wire-harness manufacturing process with a paced conveyor, but the proposed algorithm can handle continuous conveyors as well. The results confirm that the application of the proposed algorithm is widely applicable in cases where a production line of a supply chain is not well balanced and the activity times are uncertain.     

Scheduling a Single Server in a Two-machine Flow Shop

We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem. This result enables several cases of the server scheduling problem to be solved in O(n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup times are equal and there are two distinct due dates. This problem is solved in O(n ³) time when all job processing times on the first machine are equal, and it is solved in O(n ⁴) time when all processing times on the second machine are equal. Received November 20, 2001; revised October 18, 2002 Published online: January 16, 2003     

An interactive fuzzy programming approach for bi-objective straight and U-shaped assembly line balancing problem

The consideration of this paper is given to address the straight and U-shaped assembly line balancing problem. Although many attempts in the literature have been made to develop deterministic version of the assembly line model, the attention is not considerably given to those in uncertain environment. In this paper, a novel bi-objective fuzzy mixed-integer linear programming model (BOFMILP) is developed so that triangular fuzzy numbers (TFNs) are employed in order to represent uncertainty and vagueness associated with the task processing times in the real production systems. In this proposed model, two conflicting objectives (minimizing the number of stations as well as cycle time) are considered simultaneously with respect to set of constraints. For this purpose, an appropriate strategy in which new two-phase interactive fuzzy programming approach is proposed as a solution method to find an efficient compromise solution. Finally, validity of the proposed model as well as its solution approach are evaluated though numerical examples. In addition, a comparison study is conducted over some test problems in order to assess the performance of the proposed solution approach. The results demonstrate that our proposed interactive fuzzy approach not only can be applied in ALBPs but also is capable to handle any practical MOLP models. Moreover, in light of these results, the proposed model may constitute a framework aiming to assist the decision maker (DM) to deal with uncertainty in assembly line problem.     

Assembly line balancing with positional constraints,task assignment restrictions and station paralleling: A case in an electronics company

In this paper, we present a real-life Assembly Line Balancing Problem for an electronics manufacturing company. The main characteristics of the problem are as follows: (i) a set of operations are related to the front part of the workpiece and others are related to the back part of the workpiece, which in turn makes all tasks dependent on the position of the workpiece, (ii) some of the tasks must be executed on the same station and no other tasks should be assigned to this station due to technological restrictions, (iii) parallel stations are allowed to increase the line efficiency at the required production rate and to overcome the problem of assigning tasks with operation times that exceed the cycle time. Initially, the problem is formulated as a 0–1 integer programming model and solved using CPLEX solver. Then, the effect of alternative work schedules such as multiple shifts and overtime on the expected labor cost of the line is analyzed. Considering alternative work schedules while balancing the line for corresponding cycle times allows us to select an efficient assembly line for the company, resulting in a lower labor cost and a more balanced line with respect to the operation times and the activity of the workers at each station. Lastly, a computational study is conducted to evaluate the performance of the proposed model. It is found that the model is capable of producing high quality solutions in reasonable solution times.     

Job sequencing with uncertain and controllable processing times

In this paper, a single machine scheduling problem is considered. The jobs' processing times are controllable (i.e., they may take any value within a certain range) and non-precisely defined. They are treated as linguistic variables, whose values are expressed by means of fuzzy numbers. The objective function to be minimised is: (a) the mean flow time cost plus the mean processing cost, and (b) the maximum flow time cost plus the total processing cost. The problem is modelled as an assignment problem and is solved optimally with respect to the defuzzification strategy used.     

An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate

In this paper, by considering the imprecise or fuzzy nature of the data in real-world problems, job-shop scheduling problems with fuzzy processing time and fuzzy duedate are formulated and a genetic algorithm which is suitable for solving the formulated problems is proposed. On the basis of the agreement index of fuzzy duedate and fuzzy completion time, the formulated fuzzy job-shop scheduling problems are interpreted so as to maximize the minimum agreement index. For solving the formulated fuzzy job-shop scheduling problems, an efficient genetic algorithm is proposed by incorporating the concept of similarity among individuals into the genetic algorithms using the Gannt chart. As illustrative numerical examples, both 6×6 and 10×10 job-shop scheduling problems with fuzzy duedate and fuzzy processing time are considered. Through the comparative simulations with simulated annealing, the feasibility and effectiveness of the proposed method are demonstrated.     

模糊Job Shop调度交货满意度模型研究

针对生产环境中调度参数的不确定性,研究含模糊加工时间和模糊交货期的Job Shop调度问题,用6点模糊数表示加工时间梯形模糊数表示交货期。基于隶属度定义工件交货满意度,以最大化平均工件交货满意度作为优化目标建立模糊调度数学模型。基于模糊截集概念设计稳定性指标评价优化方案的稳定性,最后通过仿真结果证明所设计模型能够获得稳定性较好的满意调度方案。     

A scheduling algorithm for applications in a cloud computing system with communication changes

This paper proposes a scheduling algorithm to solve the problem of task scheduling in a cloud computing system with time‐varying communication conditions. This algorithm converts the scheduling problem with communication changes into a directed acyclic graph (DAG) scheduling problem for existing fuzzy communication task nodes, that is, the scheduling problem for a communication‐change DAG (CC‐DAG). The CC‐DAG contains both computation task nodes and communication task nodes. First, this paper proposes a weighted time‐series network bandwidth model to solve the indefinite processing time (cost) problem for a fuzzy communication task node. This model can accurately predict the processing time of a fuzzy communication task node. Second, to address the scheduling order problem for the computation task nodes, a dynamic pre‐scheduling search strategy (DPSS) is proposed. This strategy computes the essential paths for the pre‐scheduling of the computation task nodes based on the actual computation costs (times) of the computation task nodes and the predicted processing costs (times) of the fuzzy communication task nodes during the scheduling process. The computation task node with the longest essential path is scheduled first because its completion time directly influences the completion time of the task graph. Finally, we demonstrate the proposed algorithm via simulation experiments. The experimental results show that the proposed DPSS produced remarkable performance improvement rate on the total execution time that ranges between 11.5% and 21.2%. In view of the experimental results, the proposed algorithm provides better quality scheduling solution that is suitable for scientific application task execution in the cloud computing environment than HEFT, PEFT, and CEFT algorithms.     

单机模糊加工时间下最迟开工时间调度问题

研究单机模糊加工时间下确定最迟开工时间的调度问题。目标是在满足每个工作都以大于等于各自指定的隶属度属于完工集合的约束下,建筑工作的最大最迟开工时间。通过模糊数学知识对模型进行分析,对于特殊情况给出了问题的最优解,对于一般情况给出了一个最优解的必要条件。     

An effective method for solving flow shop scheduling problems with fuzzy processing times

This paper show that fuzzy set theory can be useful in modelling and solving flow shop scheduling problems with uncertain processing times and illustrates a methodology for solving job sequencing problem which the opinions of experts greatly disagree in each processing time. Triangular fuzzy numbers (TFNs) are used to represent the processing times of experts. And the comparison methods based on the dominance property is sued to determine the ranking of the fuzzy numbers. By the dominance criteria, for each job, a major TFN and a minor TFN are selected and a pessimistic sequence with major TFNs and an optimistic sequence with minor TFNs are computer. Branch and bound algorithm for makespan in three-machine flow shop is utilized to illustrate the proposed methodology.     

一种模糊项目调度问题的变宽Beam Search 算法

具有弹性约束和模糊工期的项目调度问题是一类具有实际应用意义但难于解决的问题.传统BS(Beam Search)方法存在常数线宽大小影响求解效果的问题.本文建立了此类项目调度问题的模型,并将序优化理论思想与BS方法结合,提出一种通过计算和改变线宽,兼顾解的质量和求解速度的变宽BS调度算法.仿真计算结果表明,该算法能够在较短时间内得到满意的调度结果,适用于实际模糊项目调度决策.     

A hybrid PSO/SA algorithm for bi-criteria stochastic line balancing with flexible task times and zoning constraints

This paper addresses a stochastic assembly line balancing problem with flexible task times and zoning constraints. In this problem, task times are regarded as interval variables with given lower and upper bounds. Machines can compress processing times of tasks to improve the line efficiency, but it may increase the equipment cost, which is defined via a negative linear function of task times. Thus, it is necessary to make a compromise between the line efficiency and the equipment cost. To solve this problem, a bi-objective chance-constrained mixed 0–1 programming model is developed to simultaneously minimize the cycle time and the equipment cost. Then, a hybrid Particle swarm optimization algorithm is proposed to search a set of Pareto-optimal solutions, which employs the simulated annealing as a local search strategy. The Taguchi method is used to investigate the influence of parameters, and accordingly a suitable parameter setting is suggested. Finally, the comparative results show that the proposed algorithm outperforms the existing algorithms by obtaining better solutions within the same running time.     

Comparative Corrigendum note on papers “Fuzzy adaptive GA for multi-objective assembly line balancing” continued “Modified GA for different types of assembly line balancing with fuzzy processing times”: differences and similarities [Appl. Soft Comput. 34 (September 2015) 655–677]

In the very few recently published paper by Alavidoost et al. [1], they proposed a novel fuzzy adaptive genetic algorithm for multi-objective assembly line balancing problem, in continue of their previous presented work by Alavidoost et al. [2], as a modification on genetic algorithm for assembly line balancing with fuzzy processing times. Despite the fact that both of them are well-written, and completely discussed their contributions, this note looks forward to collate these papers together. Likewise provides the correct order of the figures in [1] matching with their corresponding caption.     

A multi-objective assembly line balancing problem with worker’s skill and qualification considerations in fuzzy environment

In this study a new multi-objective assembly line balancing problem is studied. Objectives like the number of stations, the equipment purchasing cost, the worker time dependent wage, and worker dependent dis-quality level of the stations is to be minimized simultaneously with worker allocation and equipment assignment possibilities. The problem also is formulated in a fuzzy environment. To solve such problem, a new hybrid fuzzy interactive approach is proposed in two stages. In the first stage, the fuzzy formulation is converted to a crisp multi-objective formulation using a credibility-based chance constrained programming approach. Then in the second stage, the obtained crisp multi-objective formulation is solved by a new hybrid fuzzy programming approach. To evaluate the proposed approach, two generated examples and a case study from garment production industries are used for computational experiments. The extensive computational study prove the superiority of the proposed approach over the well-known approaches of the literature.     

Parametric algorithms for 2-cyclic robot scheduling with interval processing times

Consider an m-machine production line for processing identical parts served by a mobile robot. The problem is to find the minimum cycle time for 2-cyclic schedules, that is, schedules in which exactly two parts enter and two parts leave the production line during each cycle. This work treats a special case of the 2-cyclic robot scheduling problem when the robot route is given and operation durations are chosen from prescribed intervals. A strongly polynomial algorithm of time complexity O(m ⁸log m) is proposed.     

Ant colony optimization algorithm for scheduling jobs with fuzzy processing time on parallel batch machines with different capacities

We study the problem of scheduling on parallel batch processing machines with different capacities under a fuzzy environment to minimize the makespan. The jobs have non-identical sizes and fuzzy processing times. After constructing a mathematical model of the problem, we propose a fuzzy ant colony optimization (FACO) algorithm. Based on the machine capacity constraint, two candidate job lists are adopted to select the jobs for building the batches. Moreover, based on the unoccupied space of the solution, heuristic information is designed for each candidate list to guide the ants. In addition, a fuzzy local optimization algorithm is incorporated to improve the solution quality. Finally, the proposed algorithm is compared with several state-of-the-art algorithms through extensive simulated experiments and statistical tests. The comparative results indicate that the proposed algorithm can find better solutions within reasonable time than all the other compared algorithms.     

Optimal allocation of heterogeneous workers in a U-shaped production line

In this paper, we deal with a U-shaped production line with multiple heterogeneous multi-function workers. Skills of workers are assumed to be different. We consider an optimization problem for finding an allocation of workers to the line that minimizes the overall cycle time under the minimum number of workers satisfying the demand. All of processing, operation and walking times are deterministic. We propose an algorithm for computing an optimal allocation of workers to machines.