考虑分时电价的多目标批调度问题蚁群算法求解

对同时优化电力成本和制造跨度的多目标批处理机调度问题进行了研究,设计了两种多目标蚁群算法,基于工件序的多目标蚁群算法(J-PACO,Job-based Pareto Ant Colony Optimization)和基于成批的多目标蚁群算法(B-PACO,Batch-based Pareto Ant Colony Optimization)对问题进行求解分析。由于分时电价中电价是时间的函数,因而在传统批调度进行批排序的基础上,需要进一步确定批加工时间点以测定电力成本。提出的两种蚁群算法分别将工件和批与时间线相结合进行调度对此类问题进行求解。通过仿真实验将两种算法对问题的求解进行了比较,仿真实验表明B-PACO算法通过结合FFLPT(First Fit Longest Processing Time)启发式算法先将工件成批再生成最终方案,提高了算法搜索效率,并且在衡量算法搜索非支配解数量的Q指标和衡量非支配集与Pareto边界接近程度的HV指标上,均优于J-PACO算法。     

Scheduling with machine cost and rejection

In this paper we consider the scheduling problem with machine cost and rejection penalties. For this problem, we are given a sequence of independent jobs, each being characterized by its processing time (size) and its penalty. No machine is initially provided, and when a job is revealed the algorithm has the option to purchase new machines. Right when a new job arrives, we have the following choices: (i) reject it, in which case we pay its penalty; (ii) non-preemptively process it on an existing machine, which contributes to the machine load; (iii) purchase a new machine, and assign it to this machine. The objective is to minimize the sum of the makespan, the cost for purchasing machines, and the total penalty of all rejected jobs. For the small job case, (where all jobs have sizes no greater than the cost for purchasing one machine, and which is the generalization of the Ski-Rental Problem) we present an optimal online algorithm with a competitive ratio of 2.     

Development of an algorithm for the application of Group Technology in the design of Manufacturing Systems

The Group Technology theory identifies and groups similar parts into families and machines into cells, advantages being in the similarity of the parts made in each cell, and designing and manufacturing. The benefits are: simple material flow, cost reduction in material handling, reduction in work in progress, reduction in the cycle time and set-up time, increased manufacturing flexibility, increased quality, and increased job satisfaction. The objective of the work presented in this paper was to develop a Group Technology (GT) algorithm by means of cell analysis for the design of the productive system to batch production, e.g. water heater manufacturing, system manufacturing, lathes manufacturing, etc. The TGIP algorithm allows the definition of technical and economical parameters for the application of Group Technology, also taking into account the demand for the performance of the algoof heating gasrithm. The benefits of the algorithm developed are the focus on solving the case of multiple machines and the assignment of the parts to the groups related to the load of the machines; also it allows the definition of technical and economical parameters to differentiate the machines that do the same operation or even the consideration of the demand for a certain period of time.     

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.     

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.     

Heterogeneous dispatching rules in job and flow shops

This paper reports the results of a study of the use of heterogeneous dispatching rules for the scheduling of work in a job shop. The methodology employed included discrete event simulation, using rule combinations determined by prior genetic algorithm searches and generalization using neural networks. Eight dispatching rules were considered, including first in first out (FIFO), earliest due date ( EDD), shortest processing time (SPT), slack/ number of operations (SLK), critical ratio (CR), modified due date (MDD), modified operation due date (MOD), and apparent tardiness cost (ATC). A three-machine job shop was studied, in which three work organizations were employed, pure flow (fixed sequence), pure job shop ( random sequence), and a hybrid shop where flow is random but with unequal probabilities. Three levels of machine loading were used and average tardiness was used as the performance measure. In most cases, modified due date and apparent tardiness cost were the best rules. The application of the best rules effected the results primarily when applied to bottleneck machines or the first machine in a pure flow shop. Nearly any other rule was acceptable on non-botdeneck machines except FIFO and CR, which consistently perform poorly. No major advantage of mixing rules was found.     

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

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了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 Investigation of Scheduling Policies in a Dual-Constrained Manufacturing Cell*

In previous group scheduling studies, labor has essentially been ignored by assuming that enough labor is assigned to each machine in the cell. In reality, however, management usually does not have the resources to employ a laborer at each machine in the cell (i.e., machines need to share labor). Both labor scheduling and group scheduling heuristics need to be administered to manage the cell effectively. This study develops and examines scheduling procedures for a dual-constrained (i.e., machine and labor) manufacturing cell. Eleven decision rules are developed and tested under 16 different experimental conditions. The experimental factors used are interarrival time distribution, cell load, setup-to-run-time ratio, and transfer-to-run-time ratio. Results show that interarrival time distribution and cell load have the greatest impact on the performance of the cell. This suggests that effective production planning aimed at reducing job arrival variation and leveling the cell load can substantially improve cell performance. Among the experimental factors, setup and transfer-to-run-time ratio factors had the strongest influence on the rankings of the decision rules. These rankings were fairly robust across all experimental conditions and performance measures. The results also indicated that the inclusion of labor as a contraint in the cell had a significant impact on the performance of several group scheduling heuristics. Finally, it was shown that the best performing decision rules consider both transfer time and subfamily setup times.     

A note on the within-cell layout problem based on operation sequences

The existing studies in the literature usually ignore the within-cell layout problem while forming part families and manufacturing cells. A new approach is proposed to solve the part-family and machine-cell formation problem and to determine the spatial arrangement of machines in each cell simultaneously. Furthermore, a dissimilarity measure between parts based on operation sequences is presented since the operation sequences not only specify the type of machine tools needed but also impact the flow of material. As a result, we can both minimize the material handling cost and streamline the material flow in each cell.     

O(m2) ALGORITHMS FOR THE TWO AND THREE SUBLOT LOT STREAMING PROBLEM

Lot streaming is the process of splitting a job or lot into sublots to reduce its makespan on a sequence of machines. The goal in the lot streaming problem is to find the optimal size of each sublot that will minimize the makespan. The makespan is defined as the time the last sublot completes its processing on the last machine. If the sizes of these sublots are restricted to remain the same on all machines, the solution is called a consistent sublot solution. However, if the sizes of the sublots are allowed to vary, the solution is referred to as a nonconsistent or variable sublot solution. Also, if the machines must be in operation continuously from the first to the last sublot, the solution is a no idling solution. When setups are explicitly considered in the problem, there will be two cases. If setups on each machine require some portion of the first sublot be present by the machine, the problem is referred to as the attached setup time problem. If setups can be performed ahead of time before the first sublot reaches the particular machine, the corresponding problem is referred to as the detached setup problem. Finally, if the machines are allowed to be idle between the processing of sublots, the resultant solution is an intermittent idling solution. In this paper, the consistent sublot lot streaming problem with intermittent idling and no setups is discussed. The models developed also assume that the number of sublots are fixed and known. The m machine two sublot lot streaming problem is reviewed. An algorithm for the three sublot, m machine problem is derived using a network representation of the problem. The complexity of the algorithm is O (m²). Finally, using the insights from three sublot problem, a heuristic algorithm is provided for the m machine, n sublot problems. The results on the proposed heuristic are very encouraging; average percent deviation from optimal makespan is approximately at 0.76% on 155 randomly generated problems with different m and n values.     

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.     

JOB RELEASE CONTROL USING A CYCLIC SCHEDULE*

In just‐in‐time inventory management in any manufacturing setting, the general idea has been to release jobs as late as possible (to reduce inventory costs) while still having them arrive at bottleneck machines in time to maintain the desired throughput (by not starving a bottleneck machine). When a cyclic schedule is employed, the throughput is determined by a cyclic sequence of operations known as the cyclic critical path. These operations are not, in general, all performed on a single bottleneck machine. We present an algorithm for releasing jobs that treats this cyclic critical path as the bottleneck. Although this algorithm has the somewhat complex task of not delaying any of these operations on the cyclic critical path, it is greatly simplified by being able to take advantage of the fixed sequence of the cyclic schedule. The result is that the algorithm is relatively simple to implement. Although it uses a simulation‐based analysis, this analysis can all be done and the necessary results stored in advance of its use. We test the algorithm in a job shop environment with stochastic operation times. This algorithm is shown to be effective at reducing inventory while avoiding decreases in throughput.     

Multi-objective machine-component grouping in cellular manufacturing: A genetic algorithm

The cellular manufacturing system (CMS) is an important group technology (GT) application. The first step of CMS design is cell formation, generally known as machinecell formation (MCF) or machine-component (MCG). A genetic algorithm (GA) is a robust adaptive optimization method based on principles of natural evolution and is appropriate for the MCG problem, which is an NP complete complex problem. In this study, we propose a GA-based procedure to solve the MCG problem. More specifically, this study aims to minimize (1) total cost, which includes intercell and intracell part transportation costs and machines investment cots; (2) intracell machine loading imbalance; and (3) intercell machine loading imbalance under many realistic considerations. An illustrative example and comparisons demonstrate the effectiveness of this procedure. The proposed procedure is extremely adaptive, flexible, efficient and can be used to solve real MCG problems in factories by providing robust manufacturing cell formation in a short execution time.     

基于同质设备多台配置的独立生产单元构建决策

单元化生产作为一种较好实现生产柔性与生产效率融合的先进生产方式,在变种变量需求环境下它已被大量生产企业特别是装配式生产企业所采用。生产单元构建问题是单元化生产系统设计的关键问题和首要问题,也是单元化生产研究领域的一个热点。本文研究设备易复制情形下,通过配置多台同质设备来实现生产单元间无物料移动,并保证生产单元间工作量均衡的独立生产单元构建问题。本文在综合考虑换装时间、加工顺序、设备生产能力、产品需求量等多个实际生产要素的基础上,建立了以平均总流程时间和各生产单元总流程时间与平均总流程时间偏差最小为目标的数学模型,并开发了一个启发式算法来求解数学模型,最后通过数值算例验证了模型和算法的有效性。     

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.     

Energy-oriented bi-objective optimization for the tempered glass scheduling

This paper investigates a real life bi-objective hybrid flow shop scheduling problem in an energy-intensive manufacturing system, in which glass is produced successively in cutting, printing and tempering stages. The problem aims to simultaneously optimize makespan and the total electricity cost under a time-of-use electricity pricing policy. The glass production has to respect the following environments: (i) the cutting and printing operations are processed in parallel machine environments; (ii) the tempering operation is processed on a batch machine; (iii) machine eligibility and setup time have to be considered in the cutting and printing stages; (iv) the whole manufacturing system is under a time-of-use electricity pricing policy. For the problem, an integer programming model is firstly proposed and shown to be strongly NP-hard. Then a model-based heuristic is adopted and a bi-objective differential evolution algorithm (BODE) is devised based on problem features. Computational experiments on randomly generated instances demonstrated that the BODE outperforms the model-based heuristic in terms of computation time and solution quality. Moreover, with mild increase on computation burden, the BODE significantly outperforms the classic NSGA II in terms of solution quality.     

Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence

In this paper, we introduce the concept of “workload fence" into online machine rental and machine scheduling problems. With the knowledge of workload fence, online algorithms acquire the information of a finite number of first released jobs in advance. The concept originates from the frozen time fence in the domain of master scheduling in materials management. The total processing time of the jobs foreseen, corresponding to a finite number of jobs, is called workload fence, which is irrelevant to the job sequence. The remaining jobs in the sequence, however, can only become known on their arrival. This work aims to reveal whether the knowledge of workload fence helps to boost the competitive performance of deterministic online algorithms. For the online machine rental problem, we prove that the competitiveness of online algorithms can be improved with a sufficiently large workload fence. We further propose a best online algorithm for the corresponding scenario. For online parallel machine scheduling with workload fence, we give a positive answer to the above question for the case where the workload fence is equal to the length of the longest job. We also show that the competitiveness of online algorithms may not be improved even with a workload fence strictly larger than the largest length of a job. The results help one manager to make a better decision regarding the tradeoff between the performance improvement of online algorithms and the cost caused to acquire the knowledge of workload fence.

     

2-Distance vertex-distinguishing index of subcubic graphs

This paper addresses the performance of scheduling algorithms for a two-stage no-wait hybrid flowshop environment with inter-stage flexibility, where there exist several parallel machines at each stage. Each job, composed of two operations, must be processed from start to completion without any interruption either on or between the two stages. For each job, the total processing time of its two operations is fixed, and the stage-1 operation is divided into two sub-parts: an obligatory part and an optional part (which is to be determined by a solution), with a constraint that no optional part of a job can be processed in parallel with an idleness of any stage-2 machine. The objective is to minimize the makespan. We prove that even for the special case with only one machine at each stage, this problem is strongly NP-hard. For the case with one machine at stage 1 and m machines at stage 2, we propose two polynomial time approximation algorithms with worst case ratio of \(3-\frac{2}{m+1}\) and \(2-\frac{1}{m+1}\), respectively. For the case with m machines at stage 1 and one machine at stage 2, we propose a polynomial time approximation algorithm with worst case ratio of 2. We also prove that all the worst case ratios are tight.     

A simulated annealing algorithm for designing cellular manufacturing systems with productivity consideration

In this paper, we propose a productivity model for solving the machine-part grouping problem in cellular manufacturing (CM) systems. First, a non-linear 0-1 integer programming model is developed to identify machine groups and part families simultaneously. This model aims to maximize the system productivity defined as the ratio of total output to the total material handling cost. Second, an efficient simulated annealing (SA) algorithm is developed to solve large-scale problems. This algorithm provides several advantages over the existing algorithms. It forms part families and machine cells simultaneously. It also considers production volume, sales price, and maximum number of machines in each cell and total material handling cost. The proposed SA also has the ability to determine the optimum number of manufacturing cells. The performance of the developed models is tested on eight problems of different size and complexity selected from the literature. The results show the superiority of the SA algorithm over the mathematical programming model in both productivity and computational time.     

Analysis of a batch machine fed by an unreliable discrete machine

This paper analyses the behaviour of a manufacturing line consisting of two machines in series where the first machine processes lots one at a time, and is subject to failure and takes a random amount of time to repair when it fails, and the second machine is a perfectly reliable batch machine. A control limit policy is adopted to determine lot sizes for the batch machine. When the batch machine completes processing, if the number of lots in the buffer is greater than or equal to the critical number (Q?), all the lots in the buffer are loaded immediately, otherwise the batch machine waits until Q lots are accumulated. An embedded discrete time Markov-chain approach is proposed, and recursive approaches are developed to derive necessary performance measures. A numerical example explains how to obtain the optimal value of a critical number minimizing the cost functions.