一类Job- shop 车间生产计划和调度的集成优化

讨论一类Job—shop车间的生产计划和调度的集成优化问题，给出了该问题的非线性混合整数规划模型，并采用混合遗传算法进行求解。该模型利用调度约束来细化生产计划，以保证得到可行的调度解。在混合算法中，利用启发式规则来改善初始解集，并采用分段编码策略将计划和调度解映射为染色体。算例研究表明，该算法对求解该类问题具有很好的效果。     

Capacity and flexibility planning of an economical manufacturing system

This paper presents a simple dynamic model for determining the capacity and the flexibility of a manufacturing system over a finite planning horizon. We consider a problem that arises from the development phase of an investment plan for an economical manufacturing system. The objective is to minimize the total cost associated with the capacity expansion, flexibility expansion and operation. This problem is formulated as an integer program. A Lagrangian heuristic is developed for determining a near optimal solution to this integer program. Finally, we show how to incorporate aggregate production planning into the model.Based on a presentation given at the ORSA/TIMS Miami meeting in 1986.     

Capacity planning for packaging industry

This paper presents a capacity planning system (CPS) to generate a feasible production schedule, improve production efficiency, and avoid overcapacity for the packaging industry. CPS applies the concept of workload leveling and finite capacity planning to assign orders to production lines by considering several production characteristics such as drying time, quantity splitting owing to the cutting pattern of the product type, and the variability of machine capacity threshold. CPS consists of five modules, namely, order treatment module (OTM), order priority module (OPM), lot release module (LRM), workload accumulation module (WAM), and workload balance module (WBM). The experimental design is used to evaluate the effectiveness and efficiency of the proposed CPS with five factors (number of orders, order size, order size variance, order priority, and balance policy) with various levels and three response variables, namely, machine workload balance, order due date deviation, and lateness. Moreover, this result extends into finding the best settings of order priority and balance policy to generate the best favorable responses under the given three environment factors.     

Capacity planning with capability for multiple semiconductor manufacturing fabs

A capacity planning system (CPS) that considers the capacity and capability of equipment is developed for multiple semiconductor manufacturing fabs. On the basis of pull philosophy and the assumption of infinite equipment capacity, the system determines each lot's release time, start fab, and the capability of the equipment. CPS includes three main modules—the WIP-Pulling Module (WPM), the Workload Accumulation Module (WAM) and the Wafer Release Module (WRM). WPM pulls WIP from the end of the process route to meet the master production schedule (MPS). WAM then calculates the expected equipment loading in different time buckets. If WIP cannot meet the MPS requirement, then for each lot to be released, WRM evaluates the expected loading of many fabs, based on the lot's planned start time, and then determines the lot release time, the start fab and the equipment capability, to optimize the workload balance among all fabs. Simulation results indicate the effectiveness and efficiency of this system. A CPS that combines Adjusted Release Time (ART) and Path Load performs best in terms of three performance measures. This finding shows that CPS based on the combination of ART and Path Load can efficiently balance the equipment workload among the various fabs, on various days, and across various equipment at various levels of demands.     

Lagrangian bounds for just-in-time job-shop scheduling

We study the job-shop scheduling problem with earliness and tardiness penalties. We describe two Lagrangian relaxations of the problem. The first one is based on the relaxation of precedence constraints while the second one is based on the relaxation of machine constraints. We introduce dedicated algorithms to solve the corresponding dual problems. The second one is solved by a simple dynamic programming algorithm while the first one requires the resolution of an NP-hard problem by branch and bound. In both cases, the relaxations allow us to derive lower bounds as well as heuristic solutions. We finally introduce a simple local search algorithm to improve the best solution found. Computational results are reported.     

Capacity planning for IaaS cloud providers offering multiple service classes

Infrastructure as a Service (IaaS) cloud providers typically offer multiple service classes to satisfy users with different requirements and budgets. Cloud providers are faced with the challenge of estimating the minimum resource capacity required to meet Service Level Objectives (SLOs) defined for all service classes. This paper proposes a capacity planning method that is combined with an admission control mechanism to address this challenge. The capacity planning method uses analytical models to estimate the output of a quota-based admission control mechanism and find the minimum capacity required to meet availability SLOs and admission rate targets for all classes. An evaluation using trace-driven simulations shows that our method estimates the best cloud capacity with a mean relative error of 2.5% with respect to the simulation, compared to a 36% relative error achieved by a single-class baseline method that does not consider admission control mechanisms. Moreover, our method exhibited a high SLO fulfillment for both availability and admission rates, and obtained mean CPU utilization over 91%, while the single-class baseline method had values not greater than 78%.     

A memetic algorithm for the job-shop with time-lags

The job-shop with time-lags (JS|t)$(\text{<italic>JS</italic>}|t)$ is defined as a job-shop problem with minimal and maximal delays between starting times of operations. In this article, time-lags between successive operations of the same job (JS|_ti,si)$(\text{<italic>JS</italic>}|t_{i,s_i})$ are studied. This problem is a generalization of the job-shop problem (null minimal time-lags and infinite maximal time-lags) and the no-wait job-shop problem (null minimal and maximal time-lags). This article introduced a framework based on a disjunctive graph to modelize the problem and on a memetic algorithm for job sequence generation on machines.     

A neural network job-shop scheduler

This paper focuses on the development of a neural network (NN) scheduler for scheduling job-shops. In this hybrid intelligent system, genetic algorithms (GA) are used to generate optimal schedules to a known benchmark problem. In each optimal solution, every individually scheduled operation of a job is treated as a decision which contains knowledge. Each decision is modeled as a function of a set of job characteristics (e.g., processing time), which are divided into classes using domain knowledge from common dispatching rules (e.g., shortest processing time). A NN is used to capture the predictive knowledge regarding the assignment of operation’s position in a sequence. The trained NN could successfully replicate the performance of the GA on the benchmark problem. The developed NN scheduler was then tested against the GA, Attribute-Oriented Induction data mining methodology and common dispatching rules on a test set of randomly generated problems. The better performance of the NN scheduler on the test problem set compared to other methods proves the feasibility of NN-based scheduling. The scalability of the NN scheduler on larger problem sizes was also found to be satisfactory in replicating the performance of the GA.     

Problem difficulty for tabu search in job-shop scheduling

Tabu search algorithms are among the most effective approaches for solving the job-shop scheduling problem (JSP). Yet, we have little understanding of why these algorithms work so well, and under what conditions. We develop a model of problem difficulty for tabu search in the JSP, borrowing from similar models developed for SAT and other NP-complete problems. We show that the mean distance between random local optima and the nearest optimal solution is highly correlated with the cost of locating optimal solutions to typical, random JSPs. Additionally, this model accounts for the cost of locating sub-optimal solutions, and provides an explanation for differences in the relative difficulty of square versus rectangular JSPs. We also identify two important limitations of our model. First, model accuracy is inversely correlated with problem difficulty, and is exceptionally poor for rare, very high-cost problem instances. Second, the model is significantly less accurate for structured, non-random JSPs. Our results are also likely to be useful in future research on difficulty models of local search in SAT, as local search cost in both SAT and the JSP is largely dictated by the same search space features. Similarly, our research represents the first attempt to quantitatively model the cost of tabu search for any NP-complete problem, and may possibly be leveraged in an effort to understand tabu search in problems other than job-shop scheduling.     

强化学习和仿真相结合的车间作业排序系统

设计了一个强化学习和仿真相结合的动态实时车间作业排序系统．首先引入多个随机变量,将车间作业排序问题转换成序贯决策问题;然后通过仿真手段构建车间作业排序问题的模型环境,求取系统性能指标并保证解的可行性;接着设计了一个多智能体Q学习算法和仿真集成解决作业排序问题;最后通过仿真优化实验验证了该系统的有效性．     

RDLC在车间生产能力平衡中的开发与应用

制造型企业生产车间由于生产计划安排不合理．造成生产任务不能按时完成或是设备的闲置等问题,直接影响企业的经济效益。通过对某制造型企业车间管理的需求分析,将RDLC报表应用在车间能力平衡中．提供一种辅助决策工具来帮助企业对其生产能力进行有效管理,使车间生产能力和生产负荷之间达到平衡的状态,提高车间生产效率。降低车间生产成本,实现准时化生产目标。     

On the importance of sequencing decisions in production planning and scheduling

We discuss the traditional hierarchical approach to production planning and scheduling, emphasizing the fact that scheduling constraints are often either ignored or considered in a very crude way. In particular, we underline that the way scheduling is carried out is crucial for the capacity constraints on the lot sizes. Usual methods to handle capacity in theory or in practice are reviewed. Finally, we present an approach that tries to overcome these drawbacks by capturing the shop–floor capacity through scheduling considerations.     

Heuristic factory planning algorithm for advanced planning and scheduling

This study focuses on solving the factory planning (FP) problem for product structures with multiple final products. In situations in which the capacity of the work center is limited and multiple job stages are sequentially dependent, the algorithm proposed in this study is able to plan all the jobs, while minimizing delay time, cycle time, and advance time. Though mixed integer programming (MIP) is a popular way to solve supply chain factory planning problems, the MIP model becomes insolvable for complex FP problems, due to the time and computer resources required. For this reason, this study proposes a heuristic algorithm, called the heuristic factory planning algorithm (HFPA), to solve the supply chain factory planning problem efficiently and effectively. HFPA first identifies the bottleneck work center and sorts the work centers according to workload, placing the work center with the heaviest workload ahead of the others. HFPA then groups and sorts jobs according to various criteria, for example, dependency on the bottleneck work center, the workload at the bottleneck work center, and the due date. HFPA plans jobs individually in three iterations. First, it plans jobs without preempting, advancing, and/or delaying. Jobs that cannot be scheduled under these conditions are scheduled in the second iteration, which allows preemption. In the final iteration, which allows jobs to be preempted, advanced, and delayed, all the remaining jobs are scheduled. A prototype was constructed and tested to show HFPA's effectiveness and efficiency. This algorithm's power was demonstrated using computational and complexity analysis.     

An overview of function block enabled adaptive process planning for machining

Small- and medium-sized enterprises (SMEs) in job-shop machining are experiencing more shop-floor uncertainties today than ever before, due to multi-tier outsourcing, customised product demands and shortened product lifecycle. In a fluctuating shop floor environment, a process plan generated in advance is often found unsuitable or unusable to the targeted resources, resulting both in wasted effort spent in early process planning and in productivity drop when idle machines have to wait for operations to be re-planned. Consequently, an adaptive process planning approach is in demand. Targeting shop-floor uncertainty, the objective of this research is to develop a novel adaptive process planning method that can generate process plans at runtime to unplanned changes. This paper, in particular, presents an overview of adaptive process planning research and a new methodology, including two-layer system architecture, generic supervisory planning, machine-specific operation planning, and adaptive setup planning. Particularly, function blocks are introduced as a core enabling technology to bridge the gap between computer systems and CNC systems for adaptive machining.     

The activity-based aggregate production planning with capacity expansion in manufacturing systems

This paper builds a mixed integer linear programming (MILP) model to mathematically characterize the problem of aggregate production planning (APP) with capacity expansion in a manufacturing system including multiple activity centers. We use the heuristic based on capacity shifting with linear relaxation to solve the model. Two linear relaxations, i.e., a complete linear relaxation (CLR) on all the integer variables and a partial linear relaxation (PLR) on part of the integer variables are investigated and compared in computational experiments. The computational results show that the heuristic based on the capacity shifting with CLR is very fast but yields low-quality solution whereas the capacity shifting with PLR provides high-quality solutions but at the cost of considerable computational time. As a result, we develop a hybrid heuristic combining beam search with capacity shifting, which is capable of producing a high-quality solution within reasonable computational time. The computational experiment on large-scale problems suggests that when solving a practical activity-based APP model with capacity expansion at the industrial level, the capacity shifting with CLR is preferable, and the beam search heuristic could be subsequently utilized as an alternative if the relaxation gap is larger than the acceptable deviation.     

Identifying and exploiting commonalities for the job-shop scheduling problem

For many combinatorial problems the solution landscape is such that near-optimal solutions share common characteristics: the so-called commonalities or building blocks. We propose a method to identify and exploit these commonalities, which is based on applying multistart local search. In the first phase, we apply the local search heuristic, which is based on simulated annealing, to perform a set of independent runs. We discard the solutions of poor quality and compare the remaining ones to identify commonalities. In the second phase, we apply another series of independent runs in which we exploit the commonalities. We have tested this generic methodology on the so-called job-shop scheduling problem, on which many local search methods have been tested. In our computational study we found that the inclusion of commonalities in simulated annealing improves the solution quality considerably even though we found evidence that the job-shop scheduling problem is not very well suited to the use of these commonalities. Since the use of commonalities is easy to implement, it may be very useful as a standard addition to local search techniques in a general sense.     

Neural network and genetic algorithm-based hybrid approach to expanded job-shop scheduling

The expanded job-shop scheduling problem (EJSSP) is a practical production scheduling problem with processing constraints that are more restrictive and a scheduling objective that is more general than those of the standard job-shop scheduling problem (JSSP). A hybrid approach involving neural networks and genetic algorithm (GA) is presented to solve the problem in this paper. The GA is used for optimization of sequence and a neural network (NN) is used for optimization of operation start times with a fixed sequence.

After detailed analysis of an expanded job shop, new types of neurons are defined to construct a constraint neural network (CNN). The neurons can represent processing restrictions and resolve constraint conflicts. CNN with a gradient search algorithm, gradient CNN in short, is applied to the optimization of operation start times with a fixed processing sequence. It is shown that CNN is a general framework representing scheduling problems and gradient CNN can work in parallel for optimization of operation start times of the expanded job shop.

Combining gradient CNN with a GA for sequence optimization, a hybrid approach is put forward. The approach has been tested by a large number of simulation cases and practical applications. It has been shown that the hybrid approach is powerful for complex EJSSP.     

Minimizing the makespan in the non-preemptive job-shop scheduling with limited machine availability

This paper addresses the makespan minimization in a job-shop environment where the machines are not available during the whole planning horizon. The disjunctive graph model is used to represent the schedules and the concept of blocks is generalized to include the unavailability periods of machines. To solve the problem, we develop a taboo thresholding heuristic that uses a new block-based neighborhood function. Some sufficient conditions to eliminate the evaluation of non-improving moves are proposed. Experiments performed on existing problem instances of the literature show the efficiency of the proposed heuristic.     

Using job-shop scheduling tasks for evaluating collocated collaboration

Researchers have begun to explore tools that allow multiple users to collaborate across multiple devices in collocated environments. These tools often allow users to simultaneously place and interact with information on shared displays. Unfortunately, there is a lack of experimental tasks to evaluate the effectiveness of these tools for information coordination in such scenarios. In this article, we introduce job-shop scheduling as a task that could be used to evaluate systems and interactions within computer-supported collaboration environments. We describe properties that make the task useful, as well as evaluation measures that may be used. We also present two experiments as case studies to illustrate the breadth of scenarios in which this task may be applied. The first experiment shows the differences when users interact with different communicative gesturing schemes, while the second demonstrates the benefits of shared visual information on large displays. We close by discussing the general applicability of the tasks.