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.     

A simulated annealing algorithm for job shop scheduling

In this paper, the job shop scheduling problem is considered with the objective of minimization of makespan time. We first reviewed the literature on job shop scheduling using meta-heuristics. Then a simulated annealing algorithm is presented for scheduling in a job shop. To create neighbourhoods, three perturbation schemes, viz. pairwise exchange, insertion, and random insertion are used, and the effect of them on the final schedule is also compared. The proposed simulated annealing algorithm is compared with existing genetic algorithms and the comparative results are presented. For comparative evaluation, a wide variety of data sets are used. The proposed algorithm is found to perform well for scheduling in the job shop.     

The no-wait job shop with regular objective: a method based on optimal job insertion

The no-wait job shop problem (NWJS-R) considered here is a version of the job shop scheduling problem where, for any two operations of a job, a fixed time lag between their starting times is prescribed. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The problem consists in finding a schedule that minimizes a general regular objective function. We study the so-called optimal job insertion problem in the NWJS-R and prove that this problem is solvable in polynomial time by a very efficient algorithm, generalizing a result we obtained in the case of a makespan objective. We then propose a large neighborhood local search method for the NWJS-R based on the optimal job insertion algorithm and present extensive numerical results that compare favorably with current benchmarks when available.     

Taking into account the rescheduling problem during the scheduling phase

The scheduling problem in production management has been studied for a considerable time, and several types of software are used. A problem arises in updating the production planning, or ‘rescheduling’, when an unexpected event occurs in the shop control. Solving this problem is difficult because the implications of such events are usually impossible to forecast. To prevent this problem, we propose to manipulate a set of equivalent schedules during the short time schedule. Then, if an unexpected event prevents realization of a given schedule, it will be possible to find an equivalent one, without full rescheduling. The primary requirement is to find a formal representation of a set of schedules. This has already been explored using CPM graphs with nodes associated to a set of tasks. We propose in this paper to use an extension of such graphs, PQR trees, that represent both precedence and group constraints. We first reiterate the notion of PQR trees. We present methods to take into account date constraints in such a structure, and we give a model for the general job-shop problem.     

A hybrid approach to sequencing jobs using heuristic rules and neural networks

A hybrid approach to solve job sequencing problems using heuristic rules and artificial neural networks is proposed. The problem is to find a job sequence for a single machine that minimizes the total weighted tardiness of the jobs. Two different cases are considered: (1) when there are no setups, and (2) when there are sequence-dependent setup times. So far, successful heuristic rules for these cases are: apparent tardiness cost (ATC) rule proposed by Vepsalainen and Morton for the former case, and an extended version of the ATC rule (ATCS) proposed by Lee, Bhaskaran, and Pinedo for the latter. Both approaches utilize some look-ahead parameters for calculating the priority index of each job. As reported by Bhaskaran and Pinedo, the proper value of the look-ahead parameter depends upon certain problem characteristics, such as due-date tightness and due-date range. Thus, an obvious extension of the ATC or the ATCS rule is to adjust the parameter values depending upon the problem characteristics: this is known to be a difficult task. In this paper, we propose an application of a neural network as a tool to ‘predict’ proper values of the look-ahead parameters. Our computational tests show that the proposed hybrid approach outperforms both the ATC rule with a fixed parameter value and the ATCS using the heuristic curve-fitting method.     

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

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

A REVIEW OF FLOWSHOP SCHEDULING RESEARCH WITH SETUP TIMES

Flowshop scheduling problems with setup times arise naturally in many practical situations. This paper provides a review of static and deterministic flowshop scheduling research involving machine setup times. The literature is classified into four broad categories, namely sequence independent job setup times, sequence dependent job setup times, sequence independent family setup times, and sequence dependent family setup times. Using the suggested classification scheme, this paper organizes the flowshop scheduling literature involving setup and/or removal times and summarizes the existing research for different flowshop problem types. This review reveals that, while a considerable body of literature on this subject has been created, there still exist several potential areas worthy of further research.     

A COMPARISON OF ORDER-RELEASE AND DISPATCH RULES FOR THE DYNAMIC WEIGHTED EARLY/TARDY PROBLEM

The early/tardy problem is one of the most vexing pieces of the complex production scheduling decision process. So far most of the research has been on single-machine environments. Hence, we considered the weighted early/tardy scheduling problem in a simulated dynamic multimachine job shop. We analyzed controlled job-release and dispatch rules using time and cost information at a variety of stationary and nonstationary utilization rates, due-date allowances, and early/tardy cost levels. We found a newly developed method for controlling the release for all job operations using early/tardy cost information, superior to other release mechanisms overall in both our stationary and nonstationary analyses. We found immediate release useful at many high utilization conditions and a gateway-only release method best in many low utilization conditions. A modified version of a single-machine early/tardy dispatch method was clearly superior to the dispatch rules for almost all the simulated shop conditions.     

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.     

TECHNICAL NOTE: A SIMPLE MODEL FOR OPTIMIZING THE SINGLE MACHINE EARLY/TARDY PROBLEM WITH SEQUENCE-DEPENDENT SETUPS

A simple mixed integer programming model for the N job/single machine scheduling problem with possibly sequence-dependent setup times, differing earliness/tardiness cost penalties, and variable due dates is proposed and evaluated for computational efficiency. Results indicated that the computational effort required to reach optimality rose with the number of jobs to be scheduled and with decreased variance in due dates. Though computational effort was significant for the largest problems solved, the model remained viable for optimizing research scale problems.     

A STOCHASTIC DOMINANCE ORDERING OF SCHEDULING RULES

This paper applies stochastic dominance (SD) preference-ordering criteria to job shop scheduling rules. A simulation model of a hypothetical dual-constrained job shop is used to derive several measures of shop performance for a number of dispatching/due-date scheduling policies. The results presented suggest that previous research conclusions concerning the relative performance of dispatching scheduling rules may need to be reconsidered if production schedulers are risk-averse utility maximizers.     

Optimal job insertion in the no-wait job shop

The no-wait job shop (NWJS) considered here is a version of the job shop scheduling problem where, for any two operations of a job, a fixed time lag between their starting times is given. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The NWJS problem consists in finding a schedule that minimizes the makespan. We address here the so-called optimal job insertion problem (OJI) in the NWJS. While the OJI is NP-hard in the classical job shop, it was shown by Gröflin & Klinkert to be solvable in polynomial time in the NWJS. We present a highly efficient algorithm with running time $\mathcal {O}(n^{2}\cdot\max\{n,m\})$ for this problem. The algorithm is based on a compact formulation of the NWJS problem and a characterization of all feasible insertions as the stable sets (of prescribed cardinality) in a derived comparability graph. As an application of our algorithm, we propose a heuristic for the NWJS problem based on optimal job insertion and present numerical results that compare favorably with current benchmarks.     

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

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

Dynamic scheduling of manufacturing job shops using extreme value theory

Most job shop scheduling approaches reported in the literature assume that the scheduling problem is static (i.e. job arrivals and the breakdowns of machines are neglected) and in addition, these scheduling approaches may not address multiple criteria scheduling or accommodate alternate resources to process a job operation. In this paper, a scheduling method based on extreme value theory (SEVAT) is developed and addresses all the shortcomings mentioned above. The SEVAT approach creates a statistical profile of schedules through random sampling, and predicts the quality or 'potential' of a feasible schedule. A dynamic scheduling problem was designed to reflect a real job shop scheduling environment closely. Two performance measures, viz. mean job tardiness and mean job cost, were used to demonstrate multiple criteria scheduling. Three factors were identified, and varied between two levels each, thereby spanning a varied job shop environment. The results of this extensive simulation study show that the SEVAT scheduling approach produces a better performance compared to several common dispatching rules.     

Bundling and Scheduling Service Packages with Customer Behavior: Model and Heuristic

Past researchers have found evidence that customers consider the sequence of event utility when evaluating past and future service experiences. Specifically, the evidence confirms that the placement of a peak event, the utility of the last event, and the slope of event utility over time all affect customer behavior and perception. We formulate an optimization problem with a focus on optimizing schedule sequence characteristics in order to maximize customer experiences. We discuss possible contexts in which this type of scheduling might be considered and, as an example, present a particularly complex model of a world‐renowned performing arts venue. We solve the problem with a simulated annealing algorithm and further discuss the complexity and opportunities associated with this type of scheduling effort.     

一种差异工件单机批调度问题的蚁群优化算法

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization based a batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT (best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.     

An estimation of distribution algorithm for lot-streaming flow shop problems with setup times

Lot-streaming flow shops have important applications in different industries including textile, plastic, chemical, semiconductor and many others. This paper considers an n-job m-machine lot-streaming flow shop scheduling problem with sequence-dependent setup times under both the idling and no-idling production cases. The objective is to minimize the maximum completion time or makespan. To solve this important practical problem, a novel estimation of distribution algorithm (EDA) is proposed with a job permutation based representation. In the proposed EDA, an efficient initialization scheme based on the NEH heuristic is presented to construct an initial population with a certain level of quality and diversity. An estimation of a probabilistic model is constructed to direct the algorithm search towards good solutions by taking into account both job permutation and similar blocks of jobs. A simple but effective local search is added to enhance the intensification capability. A diversity controlling mechanism is applied to maintain the diversity of the population. In addition, a speed-up method is presented to reduce the computational effort needed for the local search technique and the NEH-based heuristics. A comparative evaluation is carried out with the best performing algorithms from the literature. The results show that the proposed EDA is very effective in comparison after comprehensive computational and statistical analyses.     

PRODUCTION SCHEDULING OF CONTINUOUS FLOW LINES: MULTIPLE PRODUCTS WITH SETUP TIMES AND COSTS

The problem of production planning and setup scheduling of multiple products on a single facility is studied in this paper. The facility can only produce one product at a time. A setup is required when the production switches from one type of product to another. Both setup times and setup costs are considered. The objective is to determine the setup schedule and production rate for each product that minimize the average total costs, which include the inventory, backlog, and setup costs. Under the assumption of a constant production rate, we obtain the optimal cyclic rotation schedule for the multiple products system. Besides the decision variables studied in the classical economic lot scheduling problem (ELSP), the production rate is also a decision variable in our model. We prove that our solutions improve the results of the classical ELSP.     

A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance

We study a single-machine scheduling model combining two competing agents and due-date assignment. The basic setting involves two agents who need to process their own sets of jobs, and compete on the use of a common processor. Our goal is to find the joint schedule that minimizes the value of the objective function of one agent, subject to an upper bound on the value of the objective function of the second agent. The scheduling measure considered in this paper is minimum total (earliness, tardiness and due-date) cost, based on common flow allowance, i.e., due-dates are defined as linear functions of the job processing times. We introduce a simple polynomial time solution for this problem (linear in the number of jobs), as well as to its extension to a multi-agent setting. We further extend the model to that of a due-window assignment based on common flow allowance.