SEQUENCING AND BATCHING FOR TWO CLASSES OF JOBS WITH DEADLINES AND SETUP TIMES

We formulate a general sequencing problem that includes two classes of jobs with setup times, setup costs, holding costs, and deadlines. The formulation is unique in its explicit recognition of the opportunities to exploit productive capacity increases due to batching. An algorithm based on tabu search is then used as a solution method. Computational results are presented that suggest that the algorithm is effective.     

聚类视角下的差异工件平行机批调度问题

从聚类角度研究差异工件批调度这一组合优化问题.论证了差异工件的分批问题实质为一种广义聚类问题,为求解批调度问题提供了一个全新的途径.提出了批的空间浪费比的概念,将最小化批的总加工时间目标变换为最小化批的加权空间浪费比,从而可以更容易地寻找启发式信息指导分批过程,两者的等价性也在文中给出了证明.此外,以批的空间浪费比为基...     

Synchronization of material flow to aid production planning in a job shop

This paper discusses how synchronizing finish times for correspondingly numbered process operations of mating component parts (batches) can help a job shop take advantage of some aspects of the just-in-time philosophy.This paper proposes that the synchronization of process operations of mating parts (batches) can be an effective production planning tool that may actually decrease total throughput time where manufacturers are attempting to decrease in-process inventory. An example problem is included to demonstrate the situation.A production planner must keep in perspective all production orders when trying to decrease in-process inventory. The throughput times of all orders may be increased, while too much effort is concentrated on reducing in-process inventory costs of individual orders.     

A near-optimal heuristic for the sequencing problem in multiple-batch flow-shops with small equal sublots

In this paper, we consider the lot-streaming problem of sequencing a set of batches, to be processed in equal sublots, in a flow-shop, so as to minimize makespan. A new heuristic procedure, called the bottleneck minimal idleness heuristic, is developed. Results of an experimental study are presented. It is shown that the proposed procedure generates solutions that are very close to the optimal solutions, and that the solutions generated are better than those obtained by using the fast insertion heuristic, considered to be a good heuristic for solving the flow-shop scheduling problem, when applied to the problem on hand.     

Optimizing multi-stage production with constant lot size and varying numbers of batches

The model presented in this paper assumes that a uniform lot size is produced through a series of manufacturing stages, with a single set-up and without interruption at each stage. Transportation of partial lots, called batches, is allowed between stages after the whole batch is completed. The batch sizes must be equal at any particular stage, but the optimal number of equal-sized batches may differ across stages. Of course, the set-up costs, the inventory-holding costs and the transportation costs influence both the optimal batch-sizes at the various stages and the uniform lot size. An optimization method for this deterministic model is developed and is illustrated by an example.     

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

对同时优化电力成本和制造跨度的多目标批处理机调度问题进行了研究,设计了两种多目标蚁群算法,基于工件序的多目标蚁群算法(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 PARALLEL PROCESSORS WITH SETUP COSTS AND RESOURCE LIMITATIONS

An integer linear programming model is presented for the scheduling of n products on m identical machines. The particular problem studied is one that occurs frequently in the fiberglass and textile industries. The model incorporates setup costs, lost production costs, and overtime costs. Due to the structure of the model, integer solutions can be obtained by explicitly restricting only a small number of the integer variables. This allows those responsible for scheduling to solve realistically sized problems in an efficient manner. Computational results are provided for a set of generated test problems.     

A flexibly structured lot sizing heuristic for a static remanufacturing system

An effective planning of lot sizes is a key strategy to efficiently manage a combined manufacturing/remanufacturing system in the presence of substantial setup costs. Due to its complex interdependencies, optimal policies and solutions have not been identified so far, but several heuristic approaches have been analyzed in recent contributions. The main heuristic shortcuts are forcing equally sized lot sizes over the planning horizon as well as imposing a specific cycle structure, i.e., a sequence of manufacturing batches is followed by a sequence of remanufacturing batches. We are instead proposing a flexibly structured heuristic that allows for differently sized remanufacturing batches. We show in a comprehensive numerical study that our approach outperforms other existing approaches in more than half of all instances by up to 17%.     

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

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

Integrated Order Scheduling and Packing

We consider an integrated production–distribution scheduling model in a make‐to‐order supply chain consisting of one supplier and one customer. The supplier receives a set of orders from the customer at the beginning of a planning horizon. The supplier needs to process all the orders at a single production line, pack the completed orders to form delivery batches, and deliver the batches to the customer. Each order has a weight, and the total weight of the orders packed in a batch must not exceed the capacity of the delivery batch. Each delivery batch incurs a fixed distribution cost. The problem is to find jointly a schedule for order processing and a way of packing completed orders to form delivery batches such that the total distribution cost (or equivalently, the number of delivery batches) is minimized subject to the constraint that a given customer service level is guaranteed. We consider two customer service constraints—meeting the given deadlines of the orders; or requiring the average delivery lead time of the orders to be within a given threshold. Several problems of the model with each of those constraints are considered. We clarify the complexity of each problem and develop fast heuristics for the NP‐hard problems and analyze their worst‐case performance bounds. Our computational results indicate that all the heuristics are capable of generating near optimal solutions quickly for the respective problems.     

Single machine batch scheduling with release times

Motivated by a high-throughput logging system, we investigate the single machine scheduling problem with batching, where jobs have release times and processing times, and batches require a setup time. Our objective is to minimize the total flow time, in the online setting. For the online problem where all jobs have identical processing times, we propose a 2-competitive algorithm and we prove a corresponding lower bound. Moreover, we show that if jobs with arbitrary processing times can be processed in any order, any online algorithm has a linear competitive ratio in the worst case. A preliminary version of a part of this paper was presented at the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006). We gratefully acknowledge reviewers’ comments that helped to improve the presentation of this work. Supported by the Swiss SBF under contract no. C05.0047 within COST-295 (DYNAMO) of the European Union. Research carried out while B. Weber was affiliated with the Institute of Theoretical Computer Science, ETH Zurich.     

NATURE OF PROBLEM ILL-STRUCTUREDNESS: IMPLICATIONS FOR PROBLEM FORMULATION AND SOLUTION

The distinction between ill-structured and well-structured decision problems is extended in this paper to include the degree of familiarity that a decision maker has with the initial state of the problem, its desired state, and appropriate transformations for resolving the problem. It is shown that problem ill-structuredness may result from inadequate information regarding any of these components and that the nature of problem ill-structuredness has important implications for problem formulation and solution. A decision tree is presented which represents strategies for either reformulating primary problems of each class of ill-structuredness to a more readily solved form, or solving the problem as initially formulated.     

A joint economic lot size model for raw material ordering,manufacturing setup,and finished goods delivering

In this research we consider a single-manufacturer single-buyer supply chain problem where the manufacturer orders raw materials from its supplier, then using its manufacturing processes converts the raw materials to finished goods, and finally delivers the finished goods to its customer. The manufacturer produces the product in batches at a finite rate and periodically delivers the finished goods at a fixed lot size to its customer, who has a constant demand rate. An integrated inventory control model, making joint economic lot sizes of manufacturer's raw material ordering, production batch, and buyer's ordering, is developed to minimize the mean total cost per unit time of the raw materials ordering and holding, manufacturer's setup and finished goods holding, the buyer's ordering, and inventory holding. Numerical examples are also setup to illustrate that jointly considering the inventory costs above results in less mean total cost than that of considering them separately.     

One-machine scheduling to minimize mean tardiness with minimum number tardy

In this paper the one-machine scheduling problem with the objective of minimizing the mean tardiness subject to maintaining a prescribed number of tardy jobs is analysed. An algorithm for solving this problem is presented. It is proved that the schedule generated by the proposed algorithm is indeed optimal.     

Production lot sizing model with insufficient production capacity

A mathematical model is developed for determining the optimal number of batches for the production lot sizing problem where the production capacity is lower than the annual demand requirement. Setup time is included and it is assumed that consumption begins only after the entire batch is produced. The model is illustrated through an example.     

Lot sizing in workload control systems

An important basis for workload control (WLC) is the existence of functional relationships between the mean level of work-in-process (WIP) and the values of important goal variables, like average flow time, capacity utilization, etc. These functional relationships are largely influenced by the lot sizes. This means that the usual objective of lot sizing must be supplemented by considering the impact of lot sizes on the relationships between WIP and the other goal variables. Here it is shown that this insight leads to flow time oriented lot sizing models. This type of lot sizing models is analysed. It is argued that the derivation of simple rules for lot sizing is an important research topic, and a model for deriving such rules is presented. Some rules are derived from the model, assuming that the batches are processed by an M/G/1 server, and it is shown that these rules support insights based on simulation in the 1980s. Topics for future research are outlined as well.     

Order consolidation for hierarchical product lines

We consider the batch production of hierarchical product lines in raw material industry where the whole or parts of multiple customer orders may be consolidated and processed in the same batch if their product specifications are compatible. The objective of the problem is to find maximum possible number of batches completely filled up to their capacity. The compatibility relationship among product specifications is represented by a graph called the compatibility graph. If the compatibility graph is an arbitrary graph, the problem is proven to be NP-hard and belongs to Max SNP-hard class. We develop an optimum algorithm for an important subclass of the problem where the graph is a quasi-threshold graph which in fact is the case for producing hierarchical product lines that are often found in raw materials industry.     

An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations

This paper addresses the resource-constrained project scheduling problem with uncertain activity durations. An adaptive robust optimization model is proposed to derive the resource allocation decisions that minimize the worst-case makespan, under general polyhedral uncertainty sets. The properties of the model are analyzed, assuming that the activity durations are subject to interval uncertainty where the level of robustness is controlled by a protection factor related to the risk aversion of the decision maker. A general decomposition approach is proposed to solve the robust counterpart of the resource-constrained project scheduling problem, further tailored to address the uncertainty set with the protection factor. An extensive computational study is presented on benchmark instances adapted from the PSPLIB.     

Coordinated scheduling of production and delivery stages with stage-dependent inventory holding costs

This paper considers a problem of integrated decision-making for job scheduling and delivery batching wherein different inventory holding costs between production and delivery stages are allowed. In the problem, jobs are processed on a facility at a production stage and then delivered at the subsequent delivery stage by a capacitated vehicle. The objective is to find the coordinated schedule of production and delivery that minimizes the total cost of the associated WIP inventory, finished product inventory and delivery, where both the inventory costs are characterized in terms of the weighted flow-time and the delivery cost is proportional to the required number of delivery batches. It is proved that the problem is NP-hard in the strong sense. Thereupon, three heuristic algorithms are derived. Some restricted cases are also characterized as being solvable in polynomial time. Numerical experiments are conducted to evaluate the performance of the derived heuristic algorithms.     

INTEGRATED COMPONENT AND SUPPLIER SELECTION FOR A PRODUCT FAMILY

This paper examines the reduction in complexity of a product family through product design. By leveraging the commonalities among products in a family, the decision support methodology presented in the paper helps choose components and suppliers that minimize the sum of design, procurement, and usage costs. The problem of integrated component and supplier selection is conceptualized and formulated as an integer-programming model. Analysis of the model yields two properties, complete and continuous replacement, which form the basis of a heuristic procedure. Computational tests show that the heuristic provides results close to the optimal solution and can be used for selecting components and suppliers. Application of the model to an industrial problem is discussed.