Search

We study integrated production- and delivery-scheduling problems that arise in practical make-to-order settings in several industries. In these problems, make-to-order products are first processed in a plant and then delivered to customer sites through two stages of shipping: first, from the plant to a pool point (e.g., a port, a distribution, or a consolidation center) and, second, from the pool point to customer sites. The objective is to obtain a joint schedule of job processing at the plant and two-stage shipping of completed jobs to customer sites to optimize a performance measure that takes into account both delivery timeliness and total transportation costs. We consider two problems in which delivery timeliness is measured by total or maximum lead time of the jobs and study both offline and online versions of these problems. For the offline problems involving a single production line at the plant, we provide optimal dynamic programming algorithms. For the more general offline problems involving multiple production lines at the plant, we propose fast heuristics and analyze their worst-case and asymptotic performances. For the online problems, we propose online algorithms and analyze their competitive ratios. By comparing our offline heuristics with lower bounds using randomly generated test instances, it is shown that these heuristics are capable of generating near-optimal solutions quickly. Using real data from Baosteel’s Meishan plant, we also show that our corresponding offline heuristic generates significantly better solutions than Baosteel’s rule-based approach. In addition, our computational results on the performance of the online algorithms relative to the offline heuristics generate important methodological insights that can be used by practitioners in choosing a specific solution approach.

Make-To-Order (MTO) is a popular production strategy commonly used by manufacturers selling customized products. Dynamic pricing is a popular tactical tool commonly used by sellers to match supply ...

Some airlines now offer fare-lock options, which allow passengers to hold a ticket for some time with a small fee while finalizing their travel plans. In this paper, we model passenger behavior in the presence of a fare-lock option and study the corresponding airline’s dynamic pricing problem. We prove some monotonicity properties and generate a number of managerial insights on possible implications of the fare-lock option on the airline’s revenue and optimal pricing structure, the social welfare, and the passenger surplus. We also develop an approximation algorithm that is capable of generating near-optimal solutions for large problem instances quickly.

This paper considers a truck loading and routing problem in automobile outbound logistics. Everyday, a third-party logistics (3PL) company receives a number of orders from several auto manufacturers and needs to assign the orders to available trucks which pick up the orders from the warehouses where the orders are kept and deliver them to dealers. Each order corresponds to a specific car required by a given dealer and is associated with a value and one of the three car types, small, medium or large. The value of an order is defined by whether it is an emergency order and how many days it has been waiting to be assigned to a truck. Each delivery truck is allowed to visit a pre-specified subset of cities, and is associated with a specific capacity configuration, which specifies the number of slots available for each of the three car types. The problem is to assign a subset of the orders to available trucks and create a route for each truck to maximize the total reward of the assigned orders, defined as a given weight times the total value of the assigned orders minus the total transportation cost incurred, subject to a number of constraints. A column generation based heuristic algorithm is developed where the LP relaxation of the problem is decomposed into a master problem solved by a LP solver and a number of subproblems solved by a dynamic programming based algorithm. The proposed algorithm is evaluated by comparing its solutions to upper bounds and shown to be capable of generating near-optimal solutions for practically sized problems in reasonable computational time. The algorithm is also compared to a rule-based greedy method used in practice based on real data sets from a 3PL company and shown to outperform the greedy method by a large margin.

We consider several integrated production, inventory, and delivery problems that arise in a number of practical settings where customer orders have pre-specified delivery time windows. These orders are first processed in a plant and then delivered to the customers by transporters (such as trains and air flights) which have fixed delivery departure times. If an order is completed but not immediately delivered by a transporter, the order is kept temporarily in inventory, which incurs an inventory cost. There is a delivery cost for delivering an order, which varies with the departure time. Given a set of orders, the objective is to find an integrated schedule for processing the orders, keeping finished orders in inventory if necessary, and delivering them to the customers such that the total inventory and delivery cost is minimum. We consider two classes of problems: where order delivery is splittable and where order delivery is nonsplittable. For each of the problems considered, we study its computational complexity by either showing that the problem is NP-hard or proposing an algorithm that can find an optimal solution. For the two most general problems, we show that any polynomial time algorithm has an arbitrarily bad worst-case performance bound, and propose combined column generation and tabu search heuristic algorithms that can find near optimal solutions for them in a reasonable computational time. The online appendix is available at https://doi.org/10.1287/ijoc.2016.0726 .

In this survey paper, we critique the optimization studies on the distribution of finished vehicles from automobile manufacturers to dealers in the past three decades and propose promising prospective research to minimize the gap between industrial practice and academic research. First, we identify major decision makers involved in automobile distribution, summarize service models, and briefly describe the automobile shipping practice by transportation mode. After defining the automobile shipping optimization problem at the operational level, we present the automobile distribution problem taxonomy by classifying existing studies by the level of decision making, mode of transportation, and type of optimization decisions. Each subcategory of studies is reviewed in detail through comparisons by objective function, constraints, formulation, solution algorithm, and test instances. We conclude this survey paper by summarizing major review outcomes and proposing potential research directions. This survey will stimulate interested transportation researchers to conduct further research to keep pace with the rapid evolution of the automobile shipping practice.

This paper investigates a practical batching decision problem that arises in the batch annealing operations in the cold rolling stage of steel production faced by most large iron and steel companies in the world. The problem is to select steel coils from a set of waiting coils to form batches to be annealed in available batch annealing furnaces and choose a median coil for each furnace. The objective is to maximize the total reward of the selected coils less the total coil–coil and coil–furnace mismatching cost. For a special case of the problem that arises frequently in practical settings where the coils are all similar and there is only one type of furnace available, we develop a polynomial-time dynamic programming algorithm to obtain an optimal solution. For the general case of the problem, which is strongly NP-hard, an exact branch-and-price-and-cut solution algorithm is developed using a column and row generation framework. A variable reduction strategy is also proposed to accelerate the algorithm. The algorithm is capable of solving medium-size instances to optimality within a reasonable computation time. In addition, a tabu search heuristic is proposed for solving larger instances. Three simple search neighborhoods, as well as a sophisticated variable-depth neighborhood, are developed. This heuristic can generate near-optimal solutions for large instances within a short computation time. Using both randomly generated and real-world production data sets, we show that our algorithms are superior to the typical rule-based planning approach used by many steel plants. A decision support system that embeds our algorithms was developed and implemented at Baosteel to replace their rule-based planning method. The use of the system brings significant benefits to Baosteel, including an annual net profit increase of at least 1.76 million U.S. dollars and a large reduction of standard coal consumption and carbon dioxide emissions.

In this paper, we consider a pricing problem faced by a seller that sells a given inventory of some product over a short selling horizon with limited demand information. The seller knows only that the demand is a linear function of the price, but does not know the parameters involved in the demand function. However, the seller knows that each parameter involved in the demand function belongs to a known interval. The seller’s objective is to determine the optimal price for the entire selling season to minimize the maximum regret, where the maximum regret is defined as the maximum possible loss of revenue due to not knowing the precise values of the parameters. We derive closed-form optimal solutions for the problem under all possible cases of input parameters and identify some structural properties of the solution. We conduct computational tests to compare our modeling approach with several benchmark approaches and report related insights.

Both for-profit and nonprofit peer-to-peer (P2P) ridesharing services have gained enormous popularity in recent years due to their advantages over solo driving and public transit. We study the rideshare matching and routing problem in a nonprofit P2P ridesharing system consisting of a matching agency, drivers and riders. The matching agency is a government or a not-for-profit organization and its objective is to maximize the societal benefits of ridesharing. The drivers involved are commuters and hence have their own travel plans, which are executed regardless of whether riders are matched with them. We consider both static and dynamic versions of the nonprofit P2P ridesharing problem. Existing modeling and solution approaches for similar P2P ridesharing problems can only solve relatively small problem instances optimally. We propose an exact solution algorithm for the static version of the problem by taking advantage of its special characteristics. This exact solution approach formulates and solves the problem as a set packing formulation using route-based variables, and uses an efficient graph-based approach to generate all necessary vehicle routes in the formulation quickly. We also develop a column generation (CG) based heuristic approach for the static problem. Finally, we propose two dynamic dispatching policies for the dynamic version of the problem. Our proposed exact algorithm solves very large problem instances (e.g., with 600 drivers and 1800 riders) of the static problem and our CG based heuristic can find near-optimal solutions for even larger instances of the static problem in short computation time. Our dynamic dispatching policies can generate near-optimal solutions for the dynamic problem in real-time fashion. We also generate some important insights based on some taxi trip data in Washington DC. First, P2P ridesharing can bring significant cost-saving, especially when the participants have a relatively flexible schedule. For every 10% increase in schedule flexibility, there is an about 4% to 7% increase in cost-saving. Second, the cost-saving due to ridesharing increases with the vehicle capacity, but this increase slows down quickly when the vehicle capacity reaches 4. Third, ridesharing generates more cost savings during peak hours and in urban areas.

There are a variety of joint job production and transportation scheduling problems that arise in modern manufacturing systems. In this paper, we study two such problems that arise in a flowshop environment where there are two processing stages and a single transporter that is available to deliver the finished jobs from the first stage to the second. In the first problem, there is a single machine in each of the two flowshop stages and jobs have different sizes when loaded onto the transporter. In the second problem, there are two parallel machines in the first stage and a single machine in the second stage, and the transporter can carry only one job in each shipment. The objective of both problems is to minimize the makespan, i.e., the completion time of the last job in the second stage. The two problems are both strongly NP-hard. For each problem, we propose a fast heuristic and show that the heuristic has a tight worst-case bound of 2.

This article studies a markdown optimization problem commonly faced by many large retailers that involves joint decisions on inventory allocation and markdown pricing at multiple stores subject to various business rules. At the beginning of the markdown planning horizon, there is a certain amount of inventory of a product at a warehouse that needs to be allocated to many retail stores served by the warehouse over the planning horizon. In the same time, a markdown pricing scheme needs to be determined for each store over the planning horizon. A number of business rules for inventory allocation and markdown prices at the stores must be satisfied. The retailer does not have a complete knowledge about the probability distribution of the demand at a given store in a given time period. The retailer’s knowledge about the demand distributions improves over time as new information becomes available. Hence, the retailer employs a rolling horizon approach where the problem is re-solved at the beginning of each perio...

We study an integrated charge batching and casting width selection problem arising in the continuous casting operation of the steelmaking process at Shanghai, China based Baosteel. This decision-making problem is not unique to Baosteel; it exists in every large iron and steel company in the world. We collaborated with Baosteel on this problem from 2006 to 2008 by developing and implementing a decision support system (DSS) that replaced their manual planning method. The DSS is still in active use at Baosteel. This paper describes the solution algorithms we developed and imbedded in the DSS. For the general problem that is strongly NP-hard, a column generation-based branch-and-price (B&P) solution approach is developed to obtain optimal solutions. By exploiting the problem structure, efficient dynamic programming algorithms are designed to solve the subproblems involved in the column generation procedure. Branching strategies are designed in a way that ensures that after every stage of branching the structure of the subproblems is preserved such that they can still be solved efficiently. We also consider a frequently occurring case of the problem where each steel grade is incompatible with any other grade. For this special case, a two-level polynomial-time algorithm is developed to obtain optimal solutions. Computational tests on a set of real production data as well as on a more diverse set of randomly generated problem instances show that our algorithms outperform the manual planning method that Baosteel used to use by a significant margin both in terms of tundish utilization for almost every case, and in terms of total cost for most cases. Consequently, by replacing their manual method with our DSS, the estimated benefits to Baosteel include an annual cost saving of about US $1.6 million and an annual revenue increase of about US $3.25 million.

We consider an integrated production-distribution scheduling problem in the context of a commit-to-delivery business model. The problem is strongly NP-hard. We propose a polynomial-time heuristic algorithm and show that its worst-case performance ratio is bounded by 2 and that this bound is tight.

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.

We study an integrated production and distribution scheduling model in a two-stage supply chain consisting of one or more suppliers, a warehouse, and a customer. Each supplier produces a different product at a constant rate. There is a setup time and a setup cost per production run for each supplier. Completed products are first delivered from the suppliers to the warehouse and are then sent from the warehouse to the customer. The customer's demand for each product is constant over time. The problem is to find jointly a cyclic production schedule for each supplier, a cyclic delivery schedule from each supplier to the warehouse, and a cyclic delivery schedule from the warehouse to the customer so that the customer demand for each product is satisfied without backlog at the least total production, inventory and distribution cost. We consider two production and delivery scheduling policies. We derive either an exact or a heuristic solution algorithm for the problem under each policy. Heuristics are evaluated computationally. We also evaluate the value of the warehouse by comparing our model with a model that does not have the warehouse in the supply chain (i.e. the products are delivered directly from the suppliers to the customer). Various managerial insights based on an extensive set of computational tests are reported, including how the value of warehouse and the delivery frequency from the suppliers to the warehouse are influenced by various problem parameters including production rates of the suppliers, unit inventory costs, delivery costs, and the warehouse location.

The classical scheduling literature considers many problems where a given set of jobs must be processed at minimum cost, subject to various resource constraints. The literature only considers the issue of revenue generation in a very limited way, by allowing a job to remain unprocessed and its revenue contribution to be lost. By contrast, we consider three diverse practical situations where efficient scheduling affects revenue in much more general and realistic ways. First, we study two make-to-order environments where efficient scheduling increases customer goodwill, thus stimulating demand in different ways. Second, we study two make-to-stock environments where efficient scheduling creates inventory, thus also stimulating demand in different ways. Third, we study new product markets where efficient scheduling leads to a company becoming the first mover, and thus acquiring a larger market share. In each case, we provide both a computationally efficient algorithm for scheduling and a proof that a much more efficient algorithm is unlikely to exist. For both the make-to-stock and make-to-order problems, we also describe heuristic approaches that are easy to implement, and we study their average performance. The results show that substantial benefits arise from considering the implications of efficient scheduling for revenue and net profit. The practical impact of our work is to demonstrate the importance of efficient scheduling, not only in controlling cost, but also in increasing revenue and net profit.

We study conflict and cooperation issues in supply chain manufacturing. Consider an assembly system where suppliers provide parts to a manufacturer. A product cannot be delivered until all its parts have been supplied. The manufacturer performs nonbottleneck operations, for example, outsourced assembly, packaging, and delivery for each product. Two classical scheduling objectives are considered: minimization of the total completion time and of the maximum lateness. We analyze how far from optimal the best schedule for a suppliers' scheduling problem can be for the corresponding manufacturer's problem, and vice versa. To resolve these conflicts, we consider four alternative scenarios for the relative bargaining power of the suppliers and the manufacturer, and in each case describe a practical mechanism for cooperation between the decision makers. Evaluating the cost of conflict and the benefit of cooperation in these scenarios requires the solution of various scheduling problems by the suppliers, the manufacturer, and the overall system. For all these scheduling problems, we provide either an efficient algorithm or a proof of intractability. Moreover, for two problems that we show are intractable, we describe heuristics and analyze their worst case performance or demonstrate asymptotic optimality of their solutions. We demonstrate computationally that the cost saving realized by cooperation between the decision makers is significant in many cases. Extensions of our models to consider bottleneck operations at the manufacturer and transportation times are also developed.

We consider the supply chain of a manufacturer who produces time-sensitive products that have a large variety, a short life cycle, and are sold in a very short selling season. The supply chain consists of multiple overseas plants and a domestic distribution center (DC). Retail orders are first processed at the plants and then shipped from the plants to the DC for distribution to domestic retailers. Due to variations in productivity and labor costs at different plants, the processing time and cost of an order are dependent on the plant to which it is assigned. We study the following static and deterministic order assignment and scheduling problem faced by the manufacturer before every selling season: Given a set of orders, determine which orders are to be assigned to each plant, find a schedule for processing the assigned orders at each plant, and find a schedule for shipping the completed orders from each plant to the DC, such that a certain performance measure is optimized. We consider four different performance measures, all of which take into account both delivery lead time and the total production and distribution cost. A problem corresponding to each performance measure is studied separately. We analyze the computational complexity of various cases of the problems by either proving that a problem is intractable or providing an efficient exact algorithm for the problem. We propose several fast heuristics for the intractable problems. We analyze the worst-case and asymptotic performance of the heuristics and also computationally evaluate their performance using randomly generated test instances. Our results show that the heuristics are capable of generating near-optimal solutions quickly.

Motivated by applications in the computer and food catering service industries, we study an integrated scheduling model of production and distribution operations. In this model, a set of jobs (i.e., customer orders) are first processed in a processing facility (e.g., manufacturing plant or service center) and then delivered to the customers directly without intermediate inventory. The problem is to find a joint schedule of production and distribution such that an objective function that takes into account both customer service level and total distribution cost is optimized. Customer service level is measured by a function of the times when the jobs are delivered to the customers. The distribution cost of a delivery shipment consists of a fixed charge and a variable cost proportional to the total distance of the route taken by the shipment. We study two classes of problems under this integrated scheduling model. In the first class of problems, customer service is measured by the average time when the jobs are delivered to the customers; in the second class, customer service is measured by the maximum time when the jobs are delivered to the customers. Two machine configurations in the processing facility—single machine and parallel machine—are considered. For each of the problems studied, we provide an efficient exact algorithm, or a proof of intractability accompanied by a heuristic algorithm with worst-case and asymptotic performance analysis. Computational experiments demonstrate that the heuristics developed are capable of generating near-optimal solutions. We also investigate the possible benefit of using the proposed integrated model relative to a sequential model where production and distribution operations are scheduled sequentially and separately. Computational tests show that in many cases a significant benefit can be achieved by integration.

Most deterministic production scheduling models assume that the processing time of a job on a machine is fixed externally and known in advance of scheduling. However, in most realistic situations, apart from the machines, it requires additional resources to process jobs, and the processing time of a job is determined internally by the amount of the resources allocated. In these situations, both the cost associated with the job schedule and the cost of the resources allocated should be taken into account. Therefore, job scheduling and resource allocation should be carefully coordinated and optimized jointly in order to achieve an overall cost-effective schedule. In this paper, we study a parallel-machine scheduling model involving both job processing and resource allocation. The processing time of a job is non-increasing with the cost of the allocated resources. The objective is to minimize the total cost including the cost measured by a scheduling criterion and the cost of all allocated resources. We consider two particular problems of this model, one with the scheduling criterion being the total weighted completion time, and the other with that being the weighted number of tardy jobs. We develop a column generation based branch and bound method for finding optimal solutions for these NP-hard problems. The method first formulates the problems as set partitioning type formulations, and then solves the resulting formulations exactly by branch and bound. In the branch and bound, linear relaxations of the set partitioning type formulations are decomposed into master problems and single-machine subproblems and solved by a column generation approach. The algorithms developed based on this method are capable of solving the two problems with a medium size to optimality within a reasonable computational time.

In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent or sequence dependent. We consider two particular scheduling problems relevant to such situations. In both problems, we are given a set of jobs to be processed on a set of identical parallel machines. The objective of the first problem is to minimize total weighted completion time of jobs, and that of the second problem is to minimize weighted number of tardy jobs. We propose column generation based branch and bound exact solution algorithms for the problems. Computational experiments show that the algorithms are capable of solving both problems of medium size to optimality within reasonable computational time. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 823–840, 2003.

This paper studies a scheduling problem arising in a beef distribution system where pallets of various types of beef products in the warehouse are first depalletized and then individual cases are loaded via conveyors to the trucks which deliver beef products to various customers. Given each customer's demand for each type of beef, the problem is to find a depalletizing and truck loading schedule that fills all the demands at a minimum total cost. We first show that the general problem where there are multiple trucks and each truck covers multiple customers is strongly NP-hard. Then we propose polynomial-time algorithms for the case where there are multiple trucks, each covering only one customer, and the case where there is only one truck covering multiple customers. We also develop an optimal dynamic programming algorithm and a heuristic for solving the general problem. By comparing to the optimal solutions generated by the dynamic programming algorithm, the heuristic is shown to be capable of generating near optimal solutions quickly. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003

We consider the problem of scheduling a set of nonsimultaneously available jobs on one machine. Each job has a ready time only at or after which the job can be processed. All the jobs have a common due date, which needs to be determined. The problem is to determine a due date and a schedule so as to minimize a total penalty depending on the earliness, tardiness and due date. We show that this problem is strongly NP-hard and give an efficient algorithm that finds an optimal due date and schedule when either the job sequence is predetermined or all jobs have the same processing time. We also propose three approximation algorithms for the general and special cases together with their experimental analysis.

In response to market pressures resulting in increased competition, product proliferation and greater customization, firms in many industries have adopted modern technologies to provide operational flexibility on several dimensions. In this paper, we consider the role of product mix flexibility, defined as the ability to produce a variety of products, in an environment characterized by multiple products, uncertainty in product life cycles and dynamic demands. Using a scenario-based approach for capturing the evolution of demand, we develop a stochastic programming model for determining technology choices and capacity plans. Since the resulting model is likely to be large and may not be easy to solve with standard software packages, we develop a solution procedure based on augmented Lagrangian method and restricted simplicial decomposition. The scope of our approach for deriving context specific managerial insights is illustrated by the results of limited computations. Finally, we demonstrate the versatility of our approach by deriving a special case of the general model to address some tactical issues related to new product introduction.

In this paper, we consider a machine scheduling problem where jobs should be completed at times as close as possible to their respective due dates, and hence both earliness and tardiness should be penalized. Specifically, we consider the problem with a set of independent jobs to be processed on several identical parallel machines. All the jobs have a given common due window. If a job is completed within the due window, then there is no penalty. Otherwise, there is either a job-dependent earliness penalty or a job-dependent tardiness penalty depending on whether the job is completed before or after the due window. The objective is to find an optimal schedule with minimum total earliness–tardiness penalty. The problem is known to be NP-hard. We propose a branch and bound algorithm for finding an optimal schedule of the problem. The algorithm is based on the column generation approach in which the problem is first formulated as a set partitioning type formulation and then in each branch and bound iteration the linear relaxation of this formulation is solved by the standard column generation procedure. Our computational experiments show that this algorithm is capable of solving problems with up to 40 jobs and any number of machines within a reasonable computational time.

We derive a 32-approximation algorithm for the NP-hard parallel machine total weighted completion time problem with controllable processing times by the technique of convex quadratic programming relaxation.

In most manufacturing and distribution systems, semi-finished jobs are transferred from one processing facility to another by transporters such as automated guided vehicles (AGVs) and conveyors, and finished jobs are delivered to customers or warehouses by vehicles such as trucks. Most machine scheduling models assume either that there are an infinite number of transporters for delivering jobs or that jobs are delivered instantaneously from one location to another without transportation time involved. In this paper, we study machine scheduling problems with explicit transportation considerations. Models are considered for two types of transportation situations. The first situation involves transporting a semi-finished job from one machine to another for further processing. The second appears in the environment of delivering a finished job to the customer or warehouse. Both transportation capacity and transportation times are explicitly taken into account in our models. We study this class of scheduling problems by analysing their complexity. We show that many problems are computationally difficult and propose polynomial or pseudo-polynomial algorithms for some problems. Copyright © 2001 John Wiley & Sons, Ltd.

Most machine scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines need to be maintained and hence may become unavailable during certain periods. In this paper, we study the problem of processing a set of n jobs on m parallel machines where each machine must be maintained once during the planning horizon. Our objective is to schedule jobs and maintenance activities so that the total weighted completion time of jobs is minimized. Two cases are studied in this paper. In the first case, there are sufficient resources so that different machines can be maintained simultaneously if necessary. In the second case, only one machine can be maintained at any given time. In this paper, we first show that, even when all jobs have the same weight, both cases of the problem are NP-hard. We then propose branch and bound algorithms based on the column generation approach for solving both cases of the problem. Our algorithms are capable of optimally solving medium sized problems within a reasonable computational time. We note that the general problem where at most j machines, 1 ≤ j ≤ m, can be maintained simultaneously, can be solved similarly by the column generation approach proposed in this paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 145–165, 2000

We consider a scheduling model in which several batches of jobs need to be processed by a single machine. During processing, a setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. All the jobs in the same batch have a common due date that is either externally given as an input data or internally determined as a decision variable. Two problems are investigated. One problem is to minimize the total earliness and tardiness penalties provided that each due date is externally given. We show that this problem is NP-hard even when there are only two batches of jobs and the two due dates are unrestrictively large. The other problem is to minimize the total earliness and tardiness penalties plus the total due date penalty provided that each due date is a decision variable. We give some optimality properties for this problem with the general case and propose a polynomial dynamic programming algorithm for solving this problem with two batches of jobs. We also consider a special case for both of the problems when the common due dates for different batches are all equal. Under this special case, we give a dynamic programming algorithm for solving the first problem with an unrestrictively large due date and for solving the second problem. This algorithm has a running time polynomial in the number of jobs but exponential in the number of batches.

We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on m identical parallel machines. The jobs have to be batched as well as scheduled. The completion time of a job is defined as the completion time of the batch containing it. A constant set-up time is incurred whenever a batch is formed. The problem is to batch and schedule jobs so that the total completion time of the jobs is minimized. We first present some properties and then develop a dynamic programming algorithm to solve this problem. The running time of our algorithm is O(mnm+1). When job processing times are identical, we show that the problem reduces to the corresponding single-machine problem, which has been well solved in the literature.

We consider a single-machine scheduling problem in which job processing times are controllable through the allocation of a limited resource. The amount of resource consumption of a job is assumed to be linearly related to the job processing time. The performance criteria are the total resource consumption and the number of tardy jobs. Our objective is to construct the trade-off curve between the total amount of resource consumed and the number of tardy jobs. An NP-hardness proof is presented for the problem of minimizing the total amount of allocated resource subject to a limited number of tardy jobs. A pseudo-polynomial-time dynamic programming algorithm is proposed for constructing the trade-off curve. This dynamic program can be generalized to the case where the job processing time is a decreasing function of the amount of allocated resource.

We consider a single machine scheduling problem involving both the scheduling of job processing and the scheduling of job delivery. A common due date for all the jobs and a delivery date for each job need to be determined in order to minimize the sum of earliness penalties, tardiness penalties, due date penalty, and delivery costs. Finished jobs are delivered in batches. There is no capacity limitation on a batch delivery and the cost per batch delivery is fixed and independent of the number of jobs in the batch. All the jobs completed before or at the due date are delivered in one batch at the due date. We present in this paper a polynomial dynamic programming algorithm for solving this problem.

We consider a problem of scheduling nindependent and simultaneously available jobs on munrelated parallel machines. The job processing times can be compressed through incurring an additional cost, which is a convex function of the amount of compression. Two problems are formulated as assignment problems, which can be solved inO (n3m + n2m log(nm))time. One is to minimize the total compression cost plus the total flow time. The other is to minimize the total compression cost plus the sum of earliness and tardiness costs.

Driver behavior plays a critical role in driving safety. Besides alcohol and fatigue, emotion is another factor influencing driver behavior. Thus, the detection of driver emotion can contribute to improve driving safety. In this paper, we use Bayesian Network (BNs) to develop a detection model of driver emotion with electroencephalogram (EEG), which considers two factors of driver personality and traffic situation. The preliminary experiment results suggest that this method is feasible and therefore can be used to provide adaptive aiding.

When Internet exists in the forward path and feedback path in the servo, this system can control any plant on the node of Internet at any time. Network time delay and its uncertainty property are the main impediment to develop Internet based telecontrol system. Theory and experiment prove that dynamic compensator could change Internet based telecontrol system from unstable state to stable state, but performance is influenced by predicting error of network time delay. It also can be proved by theory and experiment that variable structure compensator could weaken the steady-state error caused by more-sampled case, and improve control performance.

The paper puts forward a measuring analysis approach to studying macroscopic movement form of brain information processing. This approach doesn't research the information processing from nerve cells. It only researches the macroscopic movement form of brain information processing while the subjects make some simple logical judgments continuously in a special period according to some special instructions, researches the dynamic characteristics of movement and individual dynamic characteristics of movement, and researches the relation between the dynamic characteristics of brain information processing and the characteristics of human behavior. Because the behavior characteristics are controlled by the characteristics of brain information processing, the result of this research may be used to evaluate the ability and character of human. In engineering, it has academic instructional meaning to researching and developing the humanoid machine or all kinds of operation and control system that need human-machine matching.

We consider a broad class of machine scheduling problems that arise in a spatial setting. Machines, which might be drivers and crews, or equipment such as trucks, locomotives or aircraft, need to be assigned to a sequence of jobs over time and space. In practice, the data is often changing in real-time, and schedulers need a rapid, on-line scheduling system to assign machines to jobs. Since there is often local data available to the scheduler that may not be known to the machine, it is often more important to present a set of ranked options to the scheduler than it is to develop the “optimal” solution. In this paper, we use a linearization approximation to develop a control strategy that provides on-line control information, drawing on a concept from work in fleet management called a istics queueing network

We consider a single-machine scheduling problem in which a given number of simultaneously available items of different types are to be processed. The items must first be batched and then sequenced before processing begins. Only items of the same type can be batched together. A setup time is incurred whenever a batch of a certain type of item is formed. The flowtime of an item in a batch is defined as the completion time of the batch that contains it. The problem is to find an optimal schedule in terms of the optimal batching and sequencing decisions that minimizes the total item flowtime. We present a dynamic programming algorithm to solve this problem. The algorithm has a running time polynomial in the number of items but exponential in the number of types.

In the field of machine scheduling problems with controllable processing times, it is often assumed that the possible processing time of a job can be continuously controlled, i.e. it can be any number in a given interval. In this paper, we introduce a discrete model in which job processing times are discretely controllable, i.e. the possible processing time of a job can only be controlled to be some specified lengths. Under this discrete model, we consider a class of single machine problems with the objective of minimizing the sum of the total processing cost and the cost measured by a standard criterion. We investigate most common criteria, e.g. makespan, maximum tardiness, total completion time, weighted number of tardy jobs, and total earliness-tardiness penalty. The computational complexity of each problem is analyzed, and pseudo-polynomial dynamic programming algorithms are proposed for hard problems.