Single-machine scheduling jobs with exponential learning functions

In a manufacturing system workers are involved in doing the same job or activity repeatedly. Hence, the workers start learning more about the job or activity. Because of the learning, the time to complete the job or activity starts decreasing, which is known as “learning effect”. In this paper, an exponential sum-of-actual-processing-time based learning effect is introduced into single-machine scheduling. By the exponential sum-of-actual-processing-time based learning effect, we mean that the processing time of a job is defined by an exponential function of the sum-of-the-actual-processing-time of the already processed jobs. Under the proposed learning model, we show that under a sufficient condition, the makespan minimization problem, the sum of the θth (θ > 0) power of completion times minimization problem, and some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem remain polynomially solvable.     

基于Petri网的JSP动态优化调度

提出一种在柔性制造系统动态优化调度中处理紧急定单的方法。以带有控制器的 Petri 网为建模工具对柔性生产调度中的离散事件建模,对系统的设备维护、各种优先级等特性进行描述,利用遗传算法和模拟退火算法获得调度结果,用于解决作业车间的加工受到机床、操作工人等双资源制约条件下的动态优化调度。当有紧急定单需要加工时,该方法把剩余任务和紧急任务作为两个独立的任务分别处理,然后进行集成,在紧急任务为最优调度的基础上选取剩余任务的最优调度,找到兼顾整体和局部的最优解。仿真结果说明了算法的有效性和鲁棒性。     

Balancing high operator's workload through a new job rotation approach: Application to an automotive assembly line

Reducing musculoskeletal disorder (MSD) risk factors and work monotony are the main reasons that persuade a manufacturing industry to apply job rotation in the workforce planning. This research aims to smooth the daily workload by designing an optimal sequence of job rotation using a mathematical model. The study consists of two main steps. The first is an ergonomic analysis of the workstations to evaluate the physical workload of different jobs. An in-house risk assessment method was used to identify physical workloads of each job. In the second step, a mathematical model was developed to schedule job rotation and optimize/balance the cumulative workload. Mixed integer programming is proposed to implement a platform for the ergonomic job rotation.The objective of the job rotation programming in this research was to determine the optimal sequence of jobs for each worker such that the global daily workload of the workers would be balanced. The proposed job rotation strategy reduced the dispersion and the deviation of the daily cumulative workload among the workers considering that the rotation only occurred inside the specific groups and not between the groups.     

Design of virtual manufacturing cells: a mathematical programming approach

In this paper, a new type of virtual cellular manufacturing (CM) system is considered, and a multi-objective design procedure is developed for designing such cells in real time. Retaining the functional layout, virtual cells are addressed as temporary groupings of machines, jobs and workers to realize the benefits of CM. The virtual cells are created periodically, for instance every week or every month, depending on changes in demand volumes and mix, as new jobs accumulate during a planning period. The procedure includes labor grouping considerations in addition to part-machine grouping. The procedure is based on interactive goal programming methods. Factors such as capacity constraints, cell size restrictions, minimization of load imbalances, minimization of inter-cell movements of parts, provision of flexibility, etc. are considered. In labor grouping, the functionally specialized labor pools are partitioned and regrouped into virtual cells. Factors such as ensuring balanced loads for workers, minimization of inter-cell movements of workers, providing adequate levels of labor flexibility, etc. are considered in a pragmatic manner.     

Crew rostering with multiple goals: An empirical study

An empirical crew rostering problem drawn from the customer service section of a department store in southern Taiwan is addressed in this paper. The service section established relevant service facilities and functions to provide services for customers as well as distinguished guests and visitors. The crew rostering task is concerned with assigning multi-functional workers to different types of job and scheduling working shifts for each worker within a given time horizon, where the available and demand workforce vary from one shift to another. The current crew rostering method is a seniority orientation method. In developing the roster under current method, lines of job are generated and then bids are taken in order of decreasing seniority. The most senior worker has the widest range of job lines from which to select so as to best satisfy his/her preference. Successive crew members bid for the remaining lines of job. The current method has some drawbacks. To overcome the drawbacks, this paper develops a problem-specific approach with three stages to deal with the crew rostering problem, making it more equitable and personalized for workers by considering the management goals concerning worker–job suitability, worker–worker compatibility and worker–shift fondness. Due to the vagueness of job characteristics and the personal attributes, fuzzy method is used to improve the evaluation results of suitability, compatibility and fondness. The utility similarities of fuzzy assessments with the linguistic grade of very good are used to measure the fitness grade for the management goals. A linear goal programming model is proposed to fulfill the “efficient assignment/match from the right” policy. The proposed approach ensures the right workers are assigned to the right jobs, the right workers are placed together in a job and the pleasing working shifts are given to the workers. An illustrative application demonstrates the implementation of the proposed approach.     

A hybrid scheduling decision support model for minimizing job tardiness in a make-to-order based mould manufacturing environment

In the make-to-order (MTO) mode of manufacturing, the specification of each product is unique such that production processes vary from one product to another making the production schedule complex. In order to achieve high level productivity, the production flow is not arranged in sequence; instead, the job schedule of different production jobs is adjusted to fit in with the multiple-job shop environment. A poor scheduling of jobs leads to high production cost, long production time and tardiness in job performance. The existing of tardiness in the production schedule significantly affects the harmony among the multiple jobs on the shops floor. In order to provide a complete solution for solving MTO scheduling problems with job shifting and minimizing job tardiness, a hybrid scheduling decision support model (SDSM) is introduced. The model is combined by a Genetic Algorithm (GA) and an optimisation module. GA is adopted to solve the complex scheduling problem taking into consideration of the wide variety of processes while the optimisation module is suggested for tackling tardiness in doing the jobs in a cost effective way. The simulation results reveal that the model shortens the generation time of production schedules and reduces the production cost in MTO-based production projects.     

Scheduling of Virtual Cellular Manufacturing Systems: A Biogeography-Based Optimization Algorithm

Virtual cellular manufacturing system (VCMS) is one of the modern strategies in the production facilities layout, which has attracted considerable attention in recent years. In this system, machines are located in different positions on the shop floor and virtual cells are a logical grouping of machines, jobs, and workers from the viewpoint of the production control system. These features not only enhance the system’s agility but also allow a dynamic reassignment of cells as demand changes. This paper addresses the VCMS scheduling problems where the jobs have different orders on machines and the objective is to simultaneously minimize the weighted sum of the makespan and total traveling distance in order to create a balance between criteria. The research methodology firstly consists of a mathematical programming model with regard to the production constraints in order to describe the characteristics of the VCMS. Secondly, a basic genetic algorithm (GA), a biogeography-based optimization (BBO) algorithm, an algorithm based on hybridization of BBO and GA, and the BBO algorithm accompanied by restart phase are developed to solve the VCMS scheduling problems. The developed algorithms have been compared to each other and their performance are evaluated in terms of their best solution and computational time as effectiveness and efficiency criteria, respectively. Consequently, the performance of the best algorithm has been evaluated by the state-of-the-art algorithm, GA, in the literature. The results show that the best algorithm based on BBO could find solutions at least as good as the last famous algorithm, GA, in the literature.     

Fast reactive scheduling to minimize tardiness penalty and energy cost under power consumption uncertainties

Motivated by the need to deal with uncertainties in energy optimization of flexible manufacturing systems, this paper considers a dynamic scheduling problem which minimizes the sum of energy cost and tardiness penalty under power consumption uncertainties. An integrated control and scheduling framework is proposed including two modules, namely, an augmented discrete event control (ADEC) and a max-throughput-min-energy reactive scheduling model (MTME). The ADEC is in charge of inhibiting jobs which may lead to deadlocks, and sequencing active jobs and resources. The MTME ensures the fulfillment of the innate constraints and decides the local optimal schedule of active jobs and resources. Our proposed framework is applied to an industrial stamping system with power consumption uncertainties formulated using three different probability distributions. The obtained schedules are compared with three dispatching rules and two rescheduling approaches. Our experiment results verify that MTME outperforms three dispatching rules in terms of deviation from Pareto optimality and reduces interrupted time significantly as compared to rescheduling approaches. In addition, ADEC and MTME are programmed using the same matrix language, providing easy implementation for industrial practitioners.     

Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date

This paper considers a scheduling problem for parallel burn-in ovens in the semiconductor manufacturing industry. An oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs. We suggest three decomposition heuristics. The first heuristic applies the exact algorithm due to Emmons and Hall (for the nonbatching problem) in order to assign the jobs to separate early and tardy job sets for each of the parallel burn-in ovens. Then, we use job sequencing rules and dynamic programming in order to form batches for the early and tardy job sets and sequence them optimally. The second proposed heuristic is based on genetic algorithms. We use a genetic algorithm in order to assign jobs to each single burn-in oven. Then, after forming early and tardy job sets for each oven we apply again sequencing rules and dynamic programming techniques to the early and tardy jobs sets on each single machine in order to form batches. The third heuristic assigns jobs to the m early job sets and m tardy jobs sets in case of m burn-in ovens in parallel via a genetic algorithm and applies again dynamic programming and sequencing rules. We report on computational experiments based on generated test data and compare the results of the heuristics with known exact solution for small size test instances obtained from a branch and bound scheme.     

Improving the dynamics of five-axis machining through optimization of workpiece setup and tool orientations

Existing works in optimization of five-axis machining mainly focus on the machining efficiency and precision, while the dynamic performance of the machine tools has not been fully addressed, especially in high-speed machining, in which the rotary actuators have limited dynamic ability. In this paper, a study is reported on how to generate a tool path so that the maximal angular accelerations of the rotary axes of the five-axis machine can be reduced. Two independent methods are proposed for this task: (1) by optimizing the setup of the workpiece on the machine’s table, and (2) by finding better tilt and yaw angles for the tool orientations. In this paper, the setup parameters of the workpiece are incorporated into the inverse kinematic equations, and angular acceleration functions are established according to the numerical solutions of those equations. While varying the tool orientations unquestionably would affect the surface quality of the machining, we introduce the so called Domain of Geometric Constraints that will restrict the allowable tilt and yaw angle of the tool at the cutter contact points on the part surface, so to ensure the satisfaction of the requirement of both local-gouging-free and cusp-height. For the first method–finding the optimal workpiece setup–a heuristic-based approach, i.e., the Genetic Algorithm (GA), is adopted, whereas for the second method–the constrained optimization of tool orientations–we present an elaborate algorithm based on the results from the analysis conducted by the authors. At the end of the paper, computer simulation experiments are reported that demonstrate the effectiveness of our proposed methods and algorithms.     

Modeling and analysis of a multi-dimensional vibration isolator based on the parallel mechanism

A hybrid manipulator applied to vibration isolation of the manufacturing systems is proposed in this paper. The translations and rotations of the manipulator are decoupled, so the proposed isolator can isolate vibrations with wide range of frequency, at the same time it is fully capable of adjusting the orientations of the equipments. The scheme design, inverse kinematics, workspace and dexterity are carried out in this paper. A closed form dynamic model considering the external excitations on the base platform is performed based on the Newton–Euler approach. The optimum solutions of the forces in each actuating limb are obtained by using the Moor–Penrose inverse matrix. Furthermore, a novel dynamic performance index is proposed to evaluate the estimated maximum forces in the actuating limbs; this index can help to optimally design the parameters of motor, spring and damper. In order to evaluate the performance of isolation, the displacement transmissibility and acceleration transmissibility are also analyzed. The research work provides an analytical base for the development of the novel vibration isolator.     

Cross-training in a cellular manufacturing environment

This study addresses the need for cross-training in a cellular manufacturing environment. It is demonstrated that an effective cross-training situation results if workers and machines are connected, directly or indirectly, by task assignment decisions. The connections between workers and machines (i.e. the qualifications of workers) form ‘chains’ that can be used to reallocate work from heavily loaded workers to less loaded workers. This provides the possibility of a balanced workload situation among workers, something that is desirable from a social as well as an economic viewpoint. Based on this insight, we have developed an integer programming (IP) model that can be used to select workers to be cross-trained for particular machines. The model may help in trade-offs between training costs and the workload balance among workers in a manufacturing cell. The workload balance indicates the usefulness of labor flexibility in a particular situation. A numerical example is presented to illustrate various elements and features of the model. It also provides further insight into the role of ‘chaining’ workers and machines. The industrial applicability of the model and directions for future research are also indicated.     

An unbiased LSSVM model for classification and regression

Aiming at the common support vector machine’s biased disadvantage and computational complexity, an unbiased least squares support vector machine (LSSVM) model is proposed in this paper. The model eliminates the bias item of LSSVM by improving the form of structure risk, then the unbiased least squares support vector classifier and the unbiased least squares support vector regression are deduced. Based on this model, we design a new learning algorithm using Cholesky factorization according to the characteristic of kernel function matrix, in this way the calculation of Lagrangian multipliers is greatly simplified. Several experiments on diffenert datasets are carried out, including the common datasets classification, synthetic aperture radar image automatic target recognition and chaotic time series prediction. The experimental results of correct recognition rate and the fitting precision testify that the unbiased LSSVM model has good universal ability and fitting accuracy, better generalization capability and stability, and have a great improvement in learning speed.     

基于耦合瞬态混沌神经网络的同等并行机调度

在各种生产制造系统中都广泛存在着同等并行机调度. 本文提出了一种新的耦合瞬态混沌神经网络来求解同等并行机调度问题. 通过引入新的换位矩阵将该问题的混合整数规划模型转化为耦合瞬态神经网络的计算结构. 同时, 提出了新的计算能量函数, 使其能够包含所有约束和目标. 此外, 采用时变惩罚参数, 克服了能量函数中各惩罚项之间的权衡问题. 最后, 将该算法应用于求解 3 种不同规模的随机问题并进行仿真, 每种规模随机测试 100 次. 结果显示, 该算法能在合理的时间内收敛, 并求解出这些随机问题.     

Parallel machine match-up scheduling with manufacturing cost considerations

Many scheduling problems in practice involve rescheduling of disrupted schedules. In this study, we show that in contrast to fixed processing times, if we have the flexibility to control the processing times of the jobs, we can generate alternative reactive schedules considering the manufacturing cost implications in response to disruptions. We consider a non-identical parallel machining environment where processing times of the jobs are compressible at a certain manufacturing cost, which is a convex function of the compression on the processing time. In rescheduling it is highly desirable to catch up the original schedule as soon as possible by reassigning the jobs to the machines and compressing their processing times. On the other hand, one must also keep the manufacturing cost due to compression of the jobs low. Thus, one is faced with a tradeoff between match-up time and manufacturing cost criteria. We introduce alternative match-up scheduling problems for finding schedules on the efficient frontier of this time/cost tradeoff. We employ the recent advances in conic mixed-integer programming to model these problems effectively. We further provide a fast heuristic algorithm driven by dual prices of convex subproblems for generating approximate efficient schedules.     

Minimization of exceptional elements and voids in the cell formation problem using a multi-objective genetic algorithm

Cell formation problem is the main issue in designing cellular manufacturing systems. The most important objective in the cell formation problem is to minimize the number of exceptional elements which helps to reduce the number of intercellular movements. Another important but rarely used objective function is to minimize the number of voids inside of the machine cells. This objective function is considered in order to increase the utilization of the machines. We present a bi-objective mathematical model to simultaneously minimize the number of exceptional elements and the number of voids in the part machine incidence matrix. An ε-constraint method is then applied to solve the model and to generate the efficient solutions. Because of the NP-hardness of the model, the optimal algorithms can not be used in large-scale problems and therefore, we have also developed a bi-objective genetic algorithm. Some numerical examples are considered to illustrate the performance of the model and the effectiveness of the solution algorithms. The results demonstrate that in comparison with the ε-constraint method, the proposed genetic algorithm can obtain efficient solution in a reasonable run time.     

A metaheuristic approach for a cubic cell formation problem

The minimizations of voids and exceptional elements by considering the part-machine incidence matrix of the cell formation problem have been discussed in the literature. In recent years, a few mathematical models considering the assignment of workers to cells in addition to part and machine have been proposed to fully utilize manufacturing systems. Although the proposed mathematical models can produce the best solutions for small sized problems within reasonable times, they are inadequate to produce the best solutions for large sized real life cases due to the NP-hard nature of the problem. In this study, a genetic algorithm has been proposed for the problem of part-machine-worker cell formation. Furthermore, the Taguchi method, as a statistical optimization technique, has been used to determine the appropriate levels of the parameters. The performance of the proposed genetic algorithm has been tested using test data from the literature for small sized problems and using data that was generated in this study for large sized problems. The experimental results of this study show that the proposed genetic algorithm can produce the optimal solutions for small sized problems and that the proposed algorithm can yield optimal or near-optimal solutions for large sized problems within reasonable times.     

A goal-programming approach for design of hybrid cellular manufacturing systems in dual resource constrained environments

In this study, a goal-programming model is proposed for the design of hybrid cellular manufacturing (HCM) systems, in a dual resource constrained environment, considering many real-world application issues. The procedure consists of three phases. Following an initial phase involving a Pareto analysis of demand volumes and volatility, a machine-grouping phase is conducted to form manufacturing cells, and a residual functional layout. In this phase, over-assignment of parts to the cells, machine purchasing cost, and loss of functional synergies are attempted to be minimized. Following the formation of cells and the functional layout, a labor allocation phase is carried out by considering worker capabilities and capacities. The total costs of cross-training, hiring, firing and over-assignment of workers to more than one cell are sought to be minimized. An application of the model on real factory data is also provided in order to demonstrate the utility and possible limitations. The industrial problem was solved using professional mathematical programming software.     

Sensor deployment based on fuzzy graph considering heterogeneity and multiple-objectives to diagnose manufacturing system

In this paper, a methodology is presented to generate an optimized sensor deployment deciding sensor types, numbers, and locations to accurately monitor fault signatures in manufacturing systems. Sensor deployment to robustly monitor operation parameters is the corner stone for diagnosing manufacturing systems. However, current literature lacks investigation in methodologies that handle heterogeneity among sensor properties and consider multiple-objective optimization involved in the sensor deployment. We propose a quantitative fuzzy graph based approach to model the cause–effect relationship between system faults and sensor measurements; analytic hierarchy process (AHP) was used to aggregate the heterogeneous properties of the sensor–fault relationship into single edge values in fuzzy graph, thus quantitatively determining the sensor's detectability to fault. Finally sensor–fault matching algorithms were proposed to minimize fault unobservability and cost for the whole system, under the constraints of detectability and limited resources, thus achieving optimum sensor placement. The performance of the proposed strategy was tested and validated on different manufacturing systems (continuous or discrete); various issues discussed in the methodology were demonstrated in the case studies. In the continuous manufacturing case study, the results illustrated that compared with signed directed graph (SDG), the proposed fuzzy graph based methodology can greatly enhance the detectability to faults (from SDG's 0.699 to fuzzy graph's 0.772). In the discrete manufacturing case study, results from different optimization approaches were compared and discussed; the detectability of sensors to faults also increased from SDG's 0.61 to fuzzy graph's 0.65. The two case study results show that the proposed approach overcame the qualitative approach such as signed directed graph's deficiency on handling sensor heterogeneity and multiple objectives; the proposed approach is systematic and robust; it can be integrated into diagnosis architecture to detect faults in other complex systems.     

Work routinization and implications for ergonomic exposure assessment

Jobs in many modern settings, including manufacturing, service, agriculture and construction, are variable in their content and timing. This prompts the need for exposure assessment methods that do not assume regular work cycles. A scheme is presented for classifying levels of routinization to inform development of an appropriate exposure assessment strategy for a given occupational setting. Five levels of routinization have been defined based on the tasks of which the job is composed: 1) a single scheduled task with a regular work cycle; 2) multiple cyclical tasks; 3) a mix of cyclical and non-cyclical tasks; 4) one non-cyclical task; 5) multiple non-cyclical tasks. This classification, based primarily on job observation, is illustrated through data from a study of automobile manufacturing workers (n = 1200), from which self-assessed exposures to physical and psychosocial stressors were also obtained. In this cohort, decision latitude was greater with higher routinization level (p < 0.0001), and the least routinized jobs showed the lowest self-reported exposure to physical ergonomic stressors. The job analysis checklist developed for non-routinized jobs is presented, and limitations of the task analysis method utilized in the study are discussed. A work sampling approach to job analysis is recommended as the most efficient way to obtain a comparable unbiased exposure estimate across all routinization levels.