Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach

In today's fast-paced Just-In-Time and mass customization manufacturing in a sequence-dependent setup environment, the challenge of making production schedules to meet due-date requirements is becoming a more complex problem. Unfortunately, much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. This paper considers the problem of minimizing tardiness, a common measure of due-date performance, in a sequence-dependent setup environment. Simulated annealing was used to solve the sequencing problem, and its performance was compared with random search. Our experimental results show that the algorithm can find a good solution fairly quickly, and thus can rework schedules frequently to react to variations in the schedule. The algorithm is invaluable for ‘on-line’ production scheduling and ‘last-minute’ changes to production schedule. The results of this research also suggest ways in which more complex and realistic job shop environments, such as multiple machines with a higher number of jobs in the sequence, and other scheduling objectives can be modeled. This research also investigates computational aspects of simulated annealing in solving complex scheduling problems.     

安装时间与次序相关的生产调度干扰管理研究

在安装时间和次序相关的单机调度问题中,为应对突发性的工件优先级变动造成的影响,构建了双目标重调度模型。原目标为生产的流程时间,扰动目标为工件的加工次序扰动。针对模型中的双目标,设计了基于有效解的两阶段混合启发式算法进行求解,在原目标和扰动目标之间进行权衡。混合算法第一阶段里,基于任意单个工件次序变化将双目标问题转化成单目标TSP问题,利用最近邻域和插入混合求得单目标问题的若干解,构成初始种群。第二阶段中基于非支配排序遗传算法在处理多目标问题上的优势,对初始种群进行扩展搜索,最后输出问题的有效前沿。通过数值试验运算比较分析若干针对有效解集的指标,验证了混合算法求得的解集在多样性和临近性上要优于单纯的非支配排序遗传算法。该混合算法可以有效地解决具有安装时间的加工次序扰动问题。     

Fundamental Insights into Part Family Scheduling: The Single Machine Case

A simulation study was conducted to investigate the behavior of family scheduling procedures in a dynamic dispatching environment. Two scheduling rules that incorporate setup avoidance mechanisms (FCFS-F and SPT-F) and two that do not (FCFS and SPT) were applied to a single machine. The scheduling environment was varied by controlling several important factors: the machine utilization, the number of setup configurations (families), the size of the family setup times relative to the job run times, the frequency by which members of the part families were released for processing, and the distribution of job interarrival and job run times. The major results from the study are the following: (1) The degree of stability in the system is the most influential factor with respect to mean flow time and flow time variance. Under low variance service and interarrival time distributions, the impact of scheduling rule selection is minor. (2) Conversely, under unstable scheduling situations, family scheduling procedures can have a substantial impact. (3) Clear interaction effects are noticed between all factors. The environment most conducive to family scheduling is characterized by high resource utilization, low setup-to-run time ratio, few part families, and erratic job arrivals. (4) Under conditions favorable to family scheduling, setup avoiding procedures can be used to increase output while at the same time reduce the mean and variance of flow time. (5) The shortest processing time rule (SPT) performs well with respect to mean flow time when relative setup times are small. Overall, however, SPT-F generates the lowest mean flow time while FCFS-F produces the lowest flow time variance. This study shows that scheduling procedures that consider setups in their structure can outperform rules that do not under many different operating conditions. However, the magnitude of this advantage very much depends on the scheduling environment. The results also highlight the fact that it may be better to try to reshape the manufacturing environment than worry about selecting the correct scheduling rule. If the environment cannot be stabilized, then the choice of a setup avoiding procedure, allocation of families to machines, and setup reduction become important issues.     

A HEURISTIC ALGORITHM FOR THE FLOWSHOP PROBLEM WITH A COMMON JOB SEQUENCE ON ALL MACHINES*

This paper presents a scheduling algorithm to solve flowshop problems with a common job sequence on all machines. This algorithm uses makespan as its criterion. Initially, it chooses a preferred sequence by scanning the processing times matrix and making a few calculations. The makespan time of the preferred job-sequence is further reduced by using an improvement routine that allows interchanges between adjacent jobs. Solutions of 1200 problems are compared with the best solutions previously reported for corresponding size problems in the Campbell-Dudek-Smith (C-D-S) paper [1]. This algorithm offers up to 1% average improvement in reducing the makespan of nearly 50% of the problem sets over the results of the existing algorithms, and its computational time requirements are about one-fifth of that of the C-D-S algorithm.     

Scheduling two job families on a single machine with two competitive agents

We consider the scheduling problems arising when two agents, each with a family of jobs, compete to perform their respective jobs on a single machine. A setup time is needed for a job if it is the first job to be processed on the machine or its processing on the machine follows a job that belongs to another family. Each agent wants to minimize a certain cost function, which depends on the completion times of its jobs only. The aim is to find a schedule for all the jobs of the two agents that minimizes the objective of one agent while keeping the objective of the other agent being bounded by a fixed value \(Q\). Polynomial-time and pseudo-polynomial-time algorithms are designed to solve the problem involving various combinations of regular scheduling objective functions.     

Multi-objective permutation flow shop scheduling problem: Literature review,classification and current trends

The flow shop scheduling problem is finding a sequence given n jobs with same order at m machines according to certain performance measure(s). The job can be processed on at most one machine; meanwhile one machine can process at most one job. The most common objective for this problem is makespan. However, many real-world scheduling problems are multi-objective by nature. Over the years there have been several approaches used to deal with the multi-objective flow shop scheduling problems (MOFSP). Hence, in this study, we provide a brief literature review of the contributions to MOFSP and identify areas of opportunity for future research.     

Heuristics for scheduling in a flowshop with setup,processing and removal times separated

The problem of scheduling in a flowshop, where setup, processing and removal times are separable, is considered with the objective of minimizing makespan. Heuristic algorithms are developed by the introduction of simplifying assumptions into the scheduling problem under study. An improvement method is incorporated in the heuristics to enhance the quality of their solutions. The proposed heuristics and an existing heuristic are evaluated by a large number of randomly generated problems. The results of an extensive computational investigation for various values of parameters are presented.     

Joint Lot Sizing and Scheduling of Multiple Items with Sequence-Dependent Setup Costs

The objective of this research is to investigate the effects of setup-cost estimating methods on the lot sizing and scheduling of multiple products in multiple periods. These initial setup cost estimators (ISCEs) are used to estimate sequence-independent initial setup costs from sequence-dependent setup costs. A search of the literature reveals that, although sequence-dependent setup costs are frequently found in practice and ISCEs are frequently used, there is a dearth of research concerning the effect of using ISCEs. After a review of the literature, a mixed integer formulation of the joint problem of lot sizing and scheduling is presented, followed by a discussion of the difficulty in solving the formulation. Next, the six ISCEs evaluated are presented. These ISCEs range from simple (select the minimum setup cost) to complex (use the branch-and-bound solution to a traveling salesman-type problem). Each ISCE is evaluated using a full factorial design with five independent variables: demand distribution (three levels), demand trend (three levels), setup to inventory level (six levels), setup distribution (three levels), and setup variability (two levels). Two hypotheses are researched. Do the more computationally complex ISCEs produce lower overall costs than do the simpler ISCEs? Does the reduction in total cost justify the additional computation cost? The results of this study demonstrate that it may be incorrect to use “conventional wisdom'’when selecting an ISCE.     

考虑交货因素的热轧无缝钢管订单排程模型与算法

无缝钢管的市场需求具有多品种、小批量的特点，为了在满足客户需求的同时保证高效连续化生产，文章在满足生产工艺特征的基础上将配送地址和交货期等合同因素引入热轧无缝钢管订单排程问题中，建立了以适期交货、订单集中生产配送和最小化机器设备调整为优化目标的订单排程优化模型，并设计了两阶段求解算法：首先，以订单交货期与配送地址差异最小为目标，基于凝聚策略设计了订单聚类算法，将具有相同工艺约束、相似合同要求的订单进行聚类，并形成初始轧制计划；然后，以设备调整和提前/拖期最小为目标，设计混合变邻域搜索算法，对初始轧制批次进行排程优化。基于实际订单数据的实验结果表明，模型和算法对问题的描述和求解是可行有效的。     

GLOBAL JOB SHOP SCHEDULING WITH A GENETIC ALGORITHM

This paper describes a global job shop scheduling procedure that uses a genetic algorithm to find a good schedule. Unlike previously considered algorithms, this procedure has been implemented in the scheduling system for a manufacturing facility and has led to improved scheduling. This facility is a semiconductor test area. The test area is a job shop and has sequence-dependent setup times at some operations. The concern of management is to meet their customer due dates and to increase throughput. This requires the coordination of many resources, a task beyond the ability of simple dispatching rules. We discuss a centralized procedure that can find a good schedule through the use of a detailed scheduling model and a genetic algorithm that searches over combinations of dispatching rules. We discuss our effort in developing a system that models the shop, creates schedules for the test area personnel, and makes a number of contributions to test area management.     

Multi-objective scheduling of two-job families on a single machine

This paper presents a preliminary analysis of the typical scheduling environment in semiconductor manufacturing involving multiple job families, and where more than one objective such as cycle time, machine utilization and the due-date accuracy needs to be simultaneously considered. In this study, the NP-hard problem of scheduling N independent jobs on a single testing machine with due dates and sequence-dependent setup times is addressed, where the multiple objectives are to minimize average cycle time, to minimize average tardiness, and to maximize machine utilization. A Pareto optimal solution, which is not inferior to any other feasible solutions in terms of all objectives, is generated combining the analytically optimal and conjunctive simulated scheduling approach. First, the machine-scheduling problem is modeled using the discrete event simulation approach and the problem is divided into simulation clock based lot selection sub-problems. Then, a Pareto optimal lot is selected using the compromise programming technique for multiobjective optimization at each decision instant in simulated time. With the help of a broad experimental design, this developed solution is then compared with common heuristic-dispatching rules such as SPT and EDD, which show better results for all the objectives over a wide range of problems. The developed scheduling method shows approximately 16.7% reduction in average cycle time, 25.6% reduction in average tardiness, and 21.6% improvement in machine utilization over the common dispatching rules, SPT and EDD.     

New high performing heuristics for minimizing makespan in permutation flowshops

The well-known NEH heuristic from Nawaz, Enscore and Ham proposed in 1983 has been recognized as the highest performing method for the permutation flowshop scheduling problem under the makespan minimization criterion. This performance lead is maintained even today when compared against contemporary and more complex heuristics as shown in recent studies. In this paper we show five new methods that outperform NEH as supported by careful statistical analyses using the well-known instances of Taillard. The proposed methods try to counter the excessive greediness of NEH by carrying out re-insertions of already inserted jobs at some points in the construction of the solution. The five proposed heuristics range from extensions that are slightly slower than NEH in most tested instances to more comprehensive methods based on local search that yield excellent results at the expense of some added computational time. Additionally, NEH has been profusely used in the flowshop scheduling literature as a seed sequence in high performing metaheuristics. We demonstrate that using some of our proposed heuristics as seeds yields better final results in comparison.     

A FRAMEWORK FOR MACHINE SCHEDULING PROBLEMS WITH CONTROLLABLE PROCESSING TIMES

This is a study of single and parallel machine scheduling problems with controllable processing time for each job. The processing time for job j depends on the position of the job in the schedule and is a function of the number of resource units allocated to its processing. Processing time functions and processing cost functions are allowed to be nonlinear. The scheduling problems considered here have important applications in industry and include many of the existing scheduling models as special cases. For the single machine problem, the objective is minimization of total compression costs plus a scheduling measure. The scheduling measures include makespan, total flow time, total differences in completion times, total differences in waiting times, and total earliness and tardiness with a common due date for all jobs. Except when the total earliness and tardiness measure is involved, each case the problem is solved efficiently. Under an assumption typically satisfied in just-in-time systems, the problem with total earliness and tardiness measure is also solved efficiently. Finally, for a large class of processing time functions; parallel machine problems with total flow time and total earliness and tardiness measures are solved efficiently. In each case we reduce the problem to a transportation problem.     

A heuristic for scheduling in a flowshop with the bicriteria of makespan and maximum tardiness minimization

This article deals with the development of a heuristic for scheduling in a flowshop with the objective of minimizing the makespan and maximum tardiness of a job. The heuristic makes use of the simulated annealing technique. The proposed heuristic is relatively evaluated against the existing heuristic for scheduling to minimize the weighted sum of the makespan and maximum tardiness of a job. The results of the computational evaluation reveal that the proposed heuristic performs better than the existing one.     

Route‐Independent Analysis of Available Capacity in Flexible Manufacturing Systems

In a job shop, because of large setup times, each operation is assigned to only one machine. There is no alternative routing. In a flexible manufacturing system, each manufacturing operation can often be performed on several machines. Therefore, with automated equipment, the capacity of a machine to perform certain operations is not independent of the capacity of other machines. Often, however, operations managers can use a route‐independent answer to production planning questions. For example, how much can be produced of a certain part type and when are important capacity questions in business negotiations, when the detailed routing and scheduling are not yet of interest or cannot be known. This paper provides a mathematical model for the route‐independent analysis of the capacity of flexible manufacturing systems based on a concept of operation types. An example is provided both to illustrate the use of operation types and to highlight the differences between the traditional route‐dependent and the proposed route‐independent formulations of capacity constraints. Some computational results are also given. Finally, a sensitivity analysis is developed to analyze the feasibility of production plans when production requirements and machine capacities can change.     

Scheduling in an assembly-type production chain with batch transfer

This paper addresses a three-machine assembly-type flowshop scheduling problem, which frequently arises from manufacturing process management as well as from supply chain management. Machines one and two are arranged in parallel for producing component parts individually, and machine three is an assembly line arranged as the second stage of a flowshop for processing the component parts in batches. Whenever a batch is formed on the second-stage machine, a constant setup time is required. The objective is to minimize the makespan. In this study we establish the strong NP-hardness of the problem for the case where all the jobs have the same processing time on the second-stage machine. We then explore a useful property, based upon which a special case can be optimally solved in polynomial time. We also study several heuristic algorithms to generate quality approximate solutions for the general problem. Computational experiments are conducted to evaluate the effectiveness of the algorithms.     

An integer programming approach to scheduling in a contaminated area

This paper presents a time-indexed integer programming formulation for scheduling dependent jobs executed by a team of workers in an area contaminated with radio-active or chemical materials. The dynamics of the harmful factor and the norms of organism recovery imply that each work period for a job should be immediately followed by a rest period for the worker executing this job and the length of the rest period depends on the start time of the corresponding work period. The problem is modeled as an NP-hard problem of scheduling on unrelated parallel processors with start time dependent processing times and different objective functions: maximum or total completion time and maximum or total tardiness. The special case of scheduling jobs executed by a single worker is also considered. Numerical examples and some computational results are reported.     

Production scheduling in SMT electronic boards assembly

This paper tackles the problem of scheduling in the assembly of SMT electronic boards. In particular, it focuses on a new scheduling method developed within the framework of an industry-university joint research project. The scheduling system aims at minimizing the makespan; this goal is achieved by reducing setup times and idle times of the machines. As an example, the outcome of a test carried out on a production mix made up of 10 board types is presented and analyzed in a summarized form.     

Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated

This paper addresses the two-machine bicriteria dynamic flowshop problem where setup time of a job is separated from its processing time and is sequenced independently. The performance considered is the simultaneous minimization of total flowtime and makespan, which is more effective in reducing the total scheduling cost compared to the single objective. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N ² + 5N variables and 7N constraints is formulated. Because the problem is known to be NP-complete, a heuristic algorithm with the complexity of O (N ³) is provided. A decision index is developed as the basis for the heuristic. Experimental results show that the proposed heuristic algorithm is effective and efficient. The average solution quality of the heuristic algorithm is above 99%. A 15-job case requires only 0.0235 s, on average, to obtain a near or even optimal solution.     

Single machine group scheduling to minimize mean flow time subject to due date constraints

This paper considers a single machine group scheduling problem. All jobs are classified into groups and the jobs within a group are processed contiguously on the machine. A sequence-independent setup time is incurred between each two consecutively scheduled groups. This paper presents a solution procedure which utilizes Smith's algorithm and a proposed modified Smith's algorithm to find an optimal job sequence and an optimal group sequence which minimizes the mean flow time of jobs subject to the constraint that no jobs are tardy. The complexity of the algorithm is shown to have a polynomial running time in the number of groups and jobs.