Papers by Keyword: Parallel Machine

Abstract: This paper considers a scheduling problem of two parallel machines with a resumable availability constraint. The objective is to minimize the makespan. The problem is NP-hard in the ordinary sense. Therefore, we need to find an approximate solution that fulfills the required error bound. To get a better approximation solution in a polynomial running time, we propose a fully polynomial-time approximation scheme (FPTAS) by trimming states space.

Abstract: This paper firstly modeled the mechanism structure of 6-DOF parallel machine, analyzed its kinematic character, and solved its kinematic inverse solution. Then, the overall control structure is proposed, and finally the control system is designed based on EVC, which achieved interpolation, drilling, grooving, and inclined plane machining of this machine. The experimental result showed that the machine can move in its workspace exactly according to the trajectory.

Abstract: This paper addresses the problem of scheduling n independent jobs processed nonpreemtively on m identical parallel machines with the objective of minimizing makespan. Since these scheduling problems are well known to be NP-hard, among various solution methodologies, heuristics are preferred most. They guarantee near-optimal solutions and due to their polynomial time algorithms require reasonable computational effort, especially for solving large problem sizes. We consider three popular heuristics, multifit, combine and listfit since the seminal work of McNaughton in 1959. We present different experimental frameworks to investigate these heuristics for a comprehensive comparative performance evaluation. We show, through computational experimentation, that listfit outperforms the multifit and combine heuristics in most of the problem instances, however, at the cost of increased time complexity. The computational results also reveal that the combine heuristic performs better than the multifit heuristic, while requiring almost similar computational effort.

Abstract: This paper considers two stage hybrid flow shop with identical parallel machine and evaluate performance of common dispatching rules; shortage processing time (SPT) longest processing time (LPT) earliness due date (EDD) and first in first out (FIFO). The objectives are to determine makespan and total tardiness have been minimized. To evaluated performance of dispatching rules, the results have been compared on each criterion. The experimental results show that SPT outperform than other rules with minimizes makespan as an objective function for all problems. On the other hand, for minimize total tardiness as an objective. The EDD rule outperform than other rules.

Abstract: In this study, we address a rescheduling problem in parallel machine environments under machines failures. To make a balance between efficiency and stability of the reschedules, we consider the total number of tardy jobs as efficiency measure and the number of jobs processed on different machines in the initial and revised schedules as a stability measure. Then a heuristic algorithm which synthesizes beam search (BS) and repair-based constraint satisfaction algorithm is developed. Numerical experiments are processed to evaluate the performance and efficiency of the proposed algorithm. The experimental results show that the proposed algorithm improves the results significantly.

Abstract: In the actual industrial engineering, machines used for processing need to be checked periodically to ensure that they can work efficiently. Thus, the novel scheduling problem for parallel machines with limited capacities is worth to study. The objective function is to maximize the last completion time of jobs. We show the problem is NP-hard at least. Furthermore, two approximation algorithms are presented, and algorithms' performances are considered through the experiments with large amounts of data.

Abstract: To analyze effects of singularity on parallel manipulator, the Jacobian matrixes were introduced as the indexes for analyzing the 3UPS/S parallel machine. The relationship between the velocity Jacobian matrix and the force-transformation matrix was established, and their equivalence was verified through the determinant and condition number’ reciprocal of the matrixes. Effects of singularity on motion accuracy, actuator forces and constrained forces were investigated within the nutation angle’range. The result showed that velocity analysis and mechanical analysis were consistent for 3UPS/S parallel machine in the aspect of singularity, and proved that the accuracy and actuator force properties were deteriorated when approach to singularity. The approach could be applied to other parallel manipulators in the research on singular problem as a reference.

Abstract: Multi-item, multi-period production systems are prevalent in traditional production and distribution settings. A dynamic lot size production scheduling model (DLSPM) for multi-Production/inventory item multi-period production system with parallel machines is proposed in this paper. A mathematical framework that extends the DLSPM to multi-Production/inventory item-multi-period production planning constrained by storage space was built. The criteria of DLSPM explore optimal production schedule with the constraints of inventory, backlogs, production and demand to minimize the total inventory costs over finite planning horizon. Demand analogous to a typical production environment considered includes dynamic deterministic and fuzzy demand. The model was tested with both deterministic and fuzzy demand spread over ten years, for five equal planning periods, with a two Production/inventory item and two parallel machine test bed. From the various demand types, several iterations (sub problems) were generated and optimality condition was then verified. To capture the imprecision that is often inherent in the estimated future demand, demand was specified by fuzzy numbers and modeled using the triangular membership function distribution. Centre of gravity defuzzification scheme was used within finite intervals to obtain defuzzified demand. Tora Operations Research software was used to run the model using a test problem. Computational results vindicate the robustness and flexibility of the approach based on the quality of the solutions obtained.

Abstract: This paper aims at exploring a new parallel machine as a configuration integration, and developing this new configuration into a series. The moving platform of this parallel machine (spindle) replaces the swivel ball joints with joint rings. In the machine processing, the rigidity of the spindle parts can be enhanced. The layer of joint rings will increase holding points of spindle components and reduce singularity of the parallel machine. The comprehensive method of machine will be used in this paper which is based on the azimuthal characteristic. Each chain of the machine will be splitted into a single opened chain for research, analyzing the azimuthal characteristic of each kinematic pair. A union method is also used to work out the motion output equation of each chain. Different chain combination and intersection method will be applied on the basis of the verification of a 5-strut parallel machine to build the parallel machine of four degrees of freedom with joint rings.

Abstract: A 5-axis parallel-serial machine tool is proposed, which consists of a 3-DOF parallel mechanism and a 2-DOF serial mechanism, and the kinematics analysis is discussed in detail based on the vector method. The size of the velocity transformation matrix is decreased. The problem of parameter coupling is resolved by adopting identity matrix and four-element vector. The relationship between the velocity and acceleration of the movable platform and the input parameters of the parallel mechanism is established. These algorithms are verified correct through ADAMS (Automatic Dynamic Analysis of Mechanical System) and can be referenced by kinematics analysis, dynamics analysis of parallel or parallel-serial machine tools, which have coupling kinematics parameters.