Cutting plane algorithms for solving a stochastic edge-partition problem

We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.     

Order acceptance and due-date quotation in low machine rates

In real manufacturing environments, some customer orders include multiple jobs. However, a single due-date should be assigned to each order. Further, machine processing rate is not constant at all times. In effect, in many manufacturing operations, the machine processing rate decreases to a subnormal level during time and needs a special type of maintenance to bring the normal state back. Due to this reduction in capacity, production schedulers may decide to reject some orders. In this paper, the novel extensive problem of selecting a subset of orders, assigning due-dates to selected orders, scheduling the selected orders and jobs within each one, and scheduling the rate-modifying maintenance is studied. The objective function is minimizing total cost of lost-sales of rejected orders together with due-date length and maximum of earliness and tardiness of selected orders. The problem is proved polynomial and an optimal approach is developed.     

Fuzzy scheduling of job orders in a two-stage flowshop with batch-processing machines

In this paper, we present a mixed-integer fuzzy programming model and a genetic algorithm (GA) based solution approach to a scheduling problem of customer orders in a mass customizing furniture industry. Independent job orders are grouped into multiple classes based on similarity in style so that the required number of setups is minimized. The family of jobs can be partitioned into batches, where each batch consists of a set of consecutively processed jobs from the same class. If a batch is assigned to one of available parallel machines, a setup is required at the beginning of the first job in that batch. A schedule defines the way how the batches are created from the independent jobs and specifies the processing order of the batches and that of the jobs within the batches. A machine can only process one job at a time, and cannot perform any processing while undergoing a setup. The proposed formulation minimizes the total weighted flowtime while fulfilling due date requirements. The imprecision associated with estimation of setup and processing times are represented by fuzzy sets.     

订单带多工类工件时的极小迟后范围问题

本文考虑下述由多工类工件组成的订单的单机排序问题：每一个客户提供一个由若干工件组成的订单,总共n个工件又分成k个类．当机器从加工某类中的工件转向加工不同于它的第i类工件时,需一调整时间si．每一订单有一给定的应交工时间,订单的完工时间定义为该定单所含全部工件完工时的时间．我们希望适当排列这n个工件,使得订单的迟后范围最小．相应这一排序问题,文中依不同的背景给出了以下二种模式：同类工件一起连续加工,工件的完工时间为其所属类中全部工件完工时的时间,用GT,Ba来表示；同类工件一起连续加工,工件的完工时间为其本身的完工时间,用GT,Ja来表示．对于这两种模式的排序同题,我们均证明了其NP-hard性并给出了对应的分枝定界算法．     

Production planning problem with sequence dependent setups as a bilevel programming problem

Each of n products is to be processed on two machines in order to satisfy known demands in each of T periods. Only one product can be processed on each machine at any given time. Each switch from one item to another requires sequence dependent setup time. The objective is to minimize the total setup time and the sum of the costs of production, storage and setup. We consider the problem as a bilevel mixed 0–1 integer programming problem. The objective of the leader is to assign the products to the machines in order to minimize the total sequence dependent setup time, while the objective of the follower is to minimize the production, storage and setup cost of the machine. We develop a heuristics based on tabu search for solving the problem. At the end, some computational results are presented.     

Minimizing Labor Requirements in a Periodic Vehicle Loading Problem

In this paper, we address a logistics problem that a manufacturer of auto parts in the north of Spain described to the authors. The manufacturer stores products in its warehouse until customers retrieve them. The customers and the manufacturer agree upon an order pickup frequency. The problem is to find the best pickup schedule, which consists of the days and times during the day that each customer is expected to retrieve his/her order. For a given planning horizon, the optimization problem is to minimize the labor requirements to load the vehicles that the customers use to pick up their orders. Heuristically, we approach this situation as a decision problem in two levels. At the first level, customers are assigned to a calendar, consisting of a set of days with the required frequency during the planning horizon. Then, for each day, the decision at the second level is to assign each customer to a time slot. The busiest time slot determines the labor requirement for a given day. Therefore, once customers have been assigned to particular days in the planning horizon, the second-level decision is a multiprocessor scheduling problem, where each time slot is the equivalent of a processor, and where the objective is to minimize the makespan. A metaheuristic procedure is developed for the problem of minimizing labor requirements in this periodic vehicle-loading problem and artificial as well as real data are used to assess its performance.     

Scheduling in a two-machine flowshop with batch processing machine(s) for earliness/tardiness measure under a common due date

This paper considers a scheduling problem for a two-machine flowshop with batch processing machine(s) (BPMs) incorporated where the earliness/tardiness (E/T) measure and a common due date are considered. It assumes that each batch has the same processing time and that the common due date is not set earlier than the total job processing time on the first machine. Under these assumptions, some solution properties are characterized for three different problem cases to derive their associated solution algorithms. For the first two cases concerned with two different machine sequences such as batch-to-discrete and batch-to-batch machine sequences, a polynomial time algorithm is derived based on some of the solution properties. For the last case concerned with discrete-to-batch machine sequence, a pseudopolynomial algorithm is exploited.     

Heuristic Approaches for a Scheduling Problem in the Plastic Molding Department of an Audio Company

A production scheduling problem for making plastic molds of hi-fi models is considered. The objective is to minimize the total machine makespan in the presence of due dates, variable lot size, multiple machine types, sequence dependent, machine dependent setup times, and inventory limits. Goal programming and load balancing are applied to select the set of machine types and assign mold types to machines, resulting in a set of single-machine scheduling problems. A mixed-integer program (MIP) is formulated for the general problem but could solve only small instances. A single-machine scheduling heuristic is designed to adopt a production sequence from a travelling salesman solution. The start time of every cycle is determined by a simplified MIP. Production cycles are defined to equalize the stockout times of mold types. A post-processing step reduces the number of setups in the last cycle. Results using real-life data are promising. Characteristics giving rise to high machine utilization are discussed.     

Customer Service vs Trim Waste in Corrugated Box Manufacture

Many approaches to the problem of arranging customer orders for cutting or corrugation have focused on the minimization of trim waste. This views the corrugator more or less in isolation. When downstream machines or customer due-dates exist, however, customer service may suffer from the desire to keep scrap at a low level. Thus, if slightly higher levels of waste were accepted, the production scheduler might be able to improve performance regarding due dates.We developed a simulation model, for Domtar Packaging Ltd, of a corrugated cardboard box factory, which included the corrugation process and four finishing machines. Customer orders were generated via empirical and theoretical probability distributions, then sent through the model according to one of several scheduling rules. This allowed the relationship between various levels of trim waste and customer service to be viewed. Results of the simulation experiments, as well as a discussion of the model itself, are given. Comments and conclusions regarding both our model and corrugator algorithms in general are presented in the light of the role of the human scheduler in plants of this type.     

工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案.     

Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time

We are interested in the problem of scheduling orders for different product types in a facility with a number of machines in parallel. Each order asks for certain amounts of various different product types which can be produced concurrently. Each product type can be produced on a subset of the machines. Two extreme cases of machine environments are of interest. In the first case, each product type can be produced on one and only one machine which is dedicated to that product type. In the second case, all machines are identical and flexible; each product type can be produced by any one of the machines. Moreover, when a machine in this case switches over from one product type to another, no setup is required. Each order has a release date and a weight. Preemptions are not allowed. The objective is minimizing the total weighted completion time of the orders. Even when all orders are available at time 0, both types of machine environments have been shown to be NP-hard for any fixed number (≥2) of machines. This paper focuses on the design and analysis of approximation algorithms for these two machine environments. We also present empirical comparisons of the various algorithms. The conclusions from the empirical analyses provide insights into the trade-offs with regard to solution quality, speed, and memory space. Electronic Supplementary Material The online version of this article () contains supplementary material, which is available to authorized users. This research is supported by the National Science Foundation through grants DMI-0300156 and DMI-0245603.     

New steps in the amazing world of sequences and schedules

In this paper we consider classical shop problems:n jobs have to be processed onm machines. The processing timep _i,j of jobi on machinej is given for all operations (i, j). Each machine can process at most one job at a time and each job can be processed at most on one machine at a given time. The machine orders are fixed (job-shop) or arbitrary (open-shop). We have to determine a feasible combination of machine and job orders, a so-called sequence, which minimizes the makespan. We introduce a partial order on the set of sequences with the property that there exists at least one optimal sequence in the set of minimal elements of this partial order independent of the given processing times. The set of minimal elements (set of irreducible sequences) can be in detail described in the case of the two machine open-shop problem. The cardinality is calculated. We will show which sequences are generated by the well-known polynomial algorithms for the construction of optimal schedules. Furthermore, we investigate the problemO∥C _max on an operation set with spanning tree structure. Supported by Deutsche Forschungsgemeinschaft, Project ScheMA     

Scheduling open shops with parallel machines to minimize total completion time

This paper explores scheduling a realistic variant of open shops with parallel machines per working stage. Since real production floors seldom employ a single machine for each operation, the regular open shop problem is very often in practice extended with a set of parallel machines at each stage. The purpose of duplicating machines in parallel is to either eliminate or to reduce the impact of bottleneck stages on the overall shop efficiency. The objective is to find the sequence which minimizes total completion times of jobs. We first formulate the problem as an effective mixed integer linear programming model, and then we employ memetic algorithms to solve the problem. We employ Taguchi method to evaluate the effects of different operators and parameters on the performance of memetic algorithm. To further enhance the memetic algorithm, we hybridize it with a simple form of simulated annealing as its local search engine. To assess the performance of the model and algorithms, we establish two computational experiments. The first one is small-sized instances by which the model and general performance of the algorithms are evaluated. The second one consists of large-sized instances by which we further evaluate the algorithms.     

Efficient algorithms for machine scheduling problems with earliness and tardiness penalties

In this paper, we study the multi-machine scheduling problem with earliness and tardiness penalties and sequence dependent setup times. This problem can be decomposed into two subproblems—sequencing and timetabling. Sequencing focuses on assigning each job to a fixed machine and determine the job sequence on each machine. We call such assignment a semi-schedule. Timetabling focuses on finding an executable schedule from the semi-schedule via idle-time insertion. Sequencing is strongly NP-hard in general. Although timetabling is polynomial-time solvable, it can become a computational bottleneck if the procedure is executed many times within a larger framework. This paper makes two contributions. We first propose a quantum improvement to the computational efficiency of the timetabling algorithm. We then apply it within a squeaky wheel optimization framework to solve the sequencing and overall problem. Finally, we demonstrate the strength of our proposed algorithms by experiments.     

Online cardinality constrained scheduling

In online load balancing problems, jobs arrive over a list. Upon arrival of a job, the algorithm is required to assign it immediately and irrevocably to a machine. We consider such a makespan minimization problem with an additional cardinality constraint, i.e., at most k jobs may be assigned to each machine, where k is a parameter of the problem. We present both upper and lower bounds on the competitive ratio of online algorithms for this problem with identical machines.     

The coordination of transportation and batching scheduling

We study a coordinated scheduling problem of production and transportation in which each job is transported to a single batching machine for further processing. There are m vehicles that transport jobs from the holding area to the batching machine. Each vehicle can transport only one job at a time. The batching machine can process a batch of jobs simultaneously where there is an upper limit on the batch size. Each batch to be processed occurs a processing cost. The problem is to find a joint schedule of production and transportation such that the sum of the total completion time and the total processing cost is optimized. For a special case of the problem where the job assignment to the vehicles is predetermined, we provide a polynomial time algorithm. For the general problem, we prove that it is NP-hard (in the ordinary sense) and present a pseudo-polynomial time algorithm. A fully polynomial time approximation scheme for the general problem is obtained by converting an especially designed pseudo-polynomial dynamic programming algorithm.     

自由作业环境下的供应链排序问题

本文研究自由作业环境下的供应链排序问题,研究供应链的上游如何安排工件在自由作业机器上加工,把加工完毕的工件分批发送给下游,使得生产排序费用和发送费用总和最少.这里,生产排序费用是用工件送到时间的函数来表示;发送费用是由发送的固定费用和与运输路径有关的变化费用所组成.本文研究以工件最大送到时间为生产排序费用的自由作业供应链排序问题,在指出问题的NP困难性后,用动态规划算法构造多项式时间近似算法,并分析算法的性能比.本文最后还对特殊情形进行了讨论.     

Optimal feedback control for dynamic systems with state constraints: An exact penalty approach

In this paper, we consider a class of nonlinear dynamic systems with terminal state and continuous inequality constraints. Our aim is to design an optimal feedback controller that minimizes total system cost and ensures satisfaction of all constraints. We first formulate this problem as a semi-infinite optimization problem. We then show that by using a new exact penalty approach, this semi-infinite optimization problem can be converted into a sequence of nonlinear programming problems, each of which can be solved using standard gradient-based optimization methods. We conclude the paper by discussing applications of our work to glider control.     

工件可自由下线最小化总完工时间的平行分批排序问题

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法.