Lane reservation optimization is important in intelligent transportation systems. Most existing studies are carried out under deterministic road conditions by assuming constant road travel time. However, road conditions vary due to various factors, resulting in uncertain road travel time. This work addresses a new reliability-based lane reservation and route design problem by considering uncertain road travel time with its known mean and covariance matrix. It aims to decide which road segments in a network should implement reserved lanes and to design routes for special time-crucial transportation tasks. The objective is to maximize transportation service reliability (i.e., the probability of completing the special tasks on time). For this problem, a novel distributionally robust optimization model is first established. To solve it, this work proposes i) an adapted sample average approximation-based approach and ii) a two-stage hierarchical heuristic algorithm based on second-order cone programming. Experimental results on an illustrative example and a real-world case demonstrate that the latter is more effective and efficient than the former. In addition, we conduct a series of parameter sensitivity analysis experiments to reveal the factors affecting lane reservation and provide optimal solutions given different parameter settings.

This paper investigates a new lane reservation problem with task merging that consists of optimally determining which lanes in a transportation network have to be reserved and designing reserved lane-based routes in the network for time-crucial transport tasks. Part of the tasks whose destinations are geographically close is merged to reduce the number of vehicles and transport costs. Reserved lanes can reduce the travel time of task vehicles passing through them, while they will generate negative impact on normal traffic, such as traffic delay to the vehicles on adjacent non-reserved lanes. The objective is to minimize the total negative impact of all reserved lanes. For this problem, two new integer linear programming (ILP) models are first developed. The complexity of the problem is proved to be NP-hard. Since commercial solver (like CPLEX) is time-consuming for solving it when the problem size increases, a fast and effective improved differential evolution algorithm (IDEA) is developed based on explored problem properties. Extensive experimental results for a real-life case and benchmark instances of up to 500 nodes in the network and 30 transport tasks show the favorable performance of the IDEA, as compared to CPLEX, differential evolution algorithm and genetic algorithm. Management insights are also drawn to support practical decision-making.

An intelligent logistics system is an important branch of intelligent transportation systems. It is a great challenge to develop efficient technologies and methodologies to improve its performance in meeting customer requirements while this is highly related to people's life quality. Its high efficiency can reduce food waste, improve food quality and safety, and enhance the competitiveness of food companies. In this paper, we investigate a new integrated planning problem for intelligent food logistics systems. Two objectives are considered: minimizing total production, inventory, and transportation cost and maximizing average food quality. For the problem, a bi-objective mixed integer linear programming model is formulated first. Then, a new method that combines an ϵ-constraint-based two-phase iterative heuristic and a fuzzy logic method is developed to solve it. Computational results on a case study and on 185 randomly generated instances with up to 100 retailers and 12 periods show the effectiveness and efficiency of the proposed method.

Maritime transportation is an important branch of intelligent transportation system (ITS). It is widely recognized that modern ITS technologies and advanced management methods, such as automated yard crane (YC) planning and scheduling, can significantly improve container terminal performance, and also impact the global performance of maritime transportation. In this paper, we investigate two YC scheduling with storage and retrieval tasks in a container block. The main contributions of this paper are: (1) container reshuffling operations and inter-crane interference constraint are both considered and (2) the dynamic processing times for retrieval containers are taken into consideration. These typical YC operation characteristics complicate the YC scheduling, and cause late delivery and economic loss. In this study, we focus on minimizing the maximum tardiness of container task and establishing an integer linear programming model. Regarding the NP-hardness nature of the problem, we develop a heuristic named dividing, sequencing, and comparing (DSC) and a genetic algorithm (GA) based on the characteristics of the problem. The computational results show the efficient performance of the developed algorithms, compared with the exact solutions via Cplex software for small size instances. The efficiency and effectiveness of DSC outperform those of GA for practical size instances.

In this paper, we consider a single item single level production planning problem with uncertain and dynamic demand. The uncertainties are modelled through the probability density function of the demand. The system is studied in a rolling-horizon framework, in which data is updated at each iteration and makes the demand non-stationary. In this context, we model a cost minimization problem using a stochastic dynamic programming approach, which allows to integrate the update of the demand density into the optimization process. We calculate the optimal production quantities in a specific case where linear regression is the forecasting method used and the production lead-time is equal to one period. We finally run a simulation to illustrate the optimality of the solution, and to show its efficiency compared to others classical production planning procedures.

This paper addresses the single-track multi-hoist cyclic scheduling problem. In most existing studies, loaded hoist moves are implicitly or explicitly assumed to start and end within the same cycle. We give a counterexample to demonstrate that the optimal solution obtained with such an assumption is not necessarily the best one among all feasible solutions, called globally optimal solution. To obtain a globally optimal solution, we propose an improved mixed integer programming (MIP) approach for the multi-hoist cyclic scheduling problem with relaxation of the above assumption. Computational results on benchmark and randomly generated instances are reported and analyzed.

There are wafer fabrication processes in cluster tools that require wafer revisiting. If a swap strategy is applied to dual-arm cluster tools handling wafer revisiting, a three-wafer periodical process is formed with three wafers completed in each period. Such a period contains three cycles in a revisiting process and three cycles in a nonrevisiting one. Hence, analysis and scheduling of such tools become very complicated. In this paper, a Petri net (PN) model is developed to describe their operations. Based on it, it is found that, if a swap strategy is applied, such tools are always in a transient state. A systematic method is then presented to analyze their performance. With the help of the proposed PN model, this work, for the first time, derives the optimality conditions of three-wafer period scheduling. Industrial application examples are given to show the results.

There are wafer fabrication processes in cluster tools that require wafer revisiting. The adoption of a swap strategy for such tools forms a 3-wafer cyclic (3-WC) period with three wafers completed in each period. It has been shown that, by such a scheduling strategy, the minimal cycle time cannot be reached for some cases. This raises a question of whether there is a scheduling method such that the performance can be improved. To answer this question, a dual-arm cluster tool with wafer revisiting is modeled by a Petri net. Based on the model, the dynamical behavior of the process is analyzed. Then, a 2-wafer cyclic (2-WC) scheduling strategy is revealed for the first time. Cycle time analysis is conducted for the proposed strategy to evaluate its performance. It shows that, for some cases, the performance obtained by a 2-WC schedule is better than that obtained by any existing 3-WC ones. Thus, they can be used to complement each other in scheduling dual-arm cluster tools with wafer revisiting. Illustrative examples are given.

Crude oil transportation is a central logistics operation in petrochemical industry because its cost represents a significant part in the cost of petrochemical products. In this paper, we consider the transportation by tankers or trucks. We show that under some realistic assumptions, this problem can be transformed into a single item lot sizing problem with limited production and inventory capacities. We develop a strongly polynomial dynamic programming algorithm to solve it. The problem of crude oil transportation is very difficult. There are few efficient methods in this domain. In the model considered in this paper, crude oil is directly shipped from a supplier port tonclient ports to satisfy customer demands overTfuture periods. The supplier port disposes a fleet of identical tankers with limited capacity. The inventory capacities of customers are limited and time-varying. The backlogging is admitted. The objective is to find an optimal shipment plan minimizing the total cost over theT-period horizon. When the number of tankers is unlimited and customer demands are independent, shipment plans of different customers become independent. This problem can be considered asnindependent problems. Each of them can be transformed into a single item lot sizing problem with limited production and inventory capacities, where tanker capacity corresponds to production capacity in classical lot sizing models. The main contributions of this paper are: 1) transformation of a transportation planning problem into a lot-sizing problem; 2) an O(T3) algorithm is proposed to solve it; and 3) the results can also be applied to terrestrial transportation with direct deliveries.

There are wafer fabrication processes in cluster tools that require revisiting. It is shown that swapping is efficient in operating a dual-arm cluster tool. For dual-arm cluster tools with wafer revisiting, if a swap strategy is applied, it forms a three wafer periodical process with three wafers completed in each period. Such a period contains three cycles in a revisiting process and another three cycles in non-revisiting process. Hence, analysis and scheduling of dual-arm cluster tools with wafer revisiting become very complicated. In this work, a Petri net model is developed to describe the operations of such tools. Based on it, it is found that if a swap strategy is applied to a dual-arm cluster tool with wafer revisiting, it is always in a transient state. A systematic method is presented to analyze its performance.

For some wafer fabrication processes in cluster tools, e.g., atomic layer deposition (ALD), wafer revisiting is required. Typically, in such processes, wafers need to visit two consecutive processing steps several times. Such a revisiting process can be denoted as (mi, mi + 1)h, where i means the ith-step and miand mi + 1mean the corresponding quantity of the processing modules in i and (i+1)th steps, and h the number of visiting times. This paper conducts a study for scheduling single-arm cluster tools with such a wafer revisiting process. The system is modeled by Petri nets (PNs) to guarantee the feasibility of robot activities. Based on the model, a deadlock avoidance policy is presented. With the control policy, cycle time analysis for the revisiting process is made. With the fact that wafer processing times are much longer than robot movement times in cluster tools, it is shown that, when mi= mi + 1= 1, i.e., each step has only one processing module, the optimal one-wafer cyclic schedule is deterministic and unique, and the minimal cycle time can be calculated by an analytical expression. It is also shown that, when mi= 1 and mi+ 1 = 2 or mi= 2 and mi+ 1 = 1, the optimal one-wafer cyclic schedule can be obtained by finding h deterministic schedules and the one with the least cycle time. A novel analytical method is finally presented to schedule the overall system containing such reentrant wafer flow. This represents a significant advance in single-arm cluster equipment automation.

For short-term scheduling of crude oil operations in refinery, often crude oil residency time constraint and charging-tank-switch-overlap constraint are ignored by mathematical programming models to make the problem solvable. Thus, a schedule obtained by such mathematical programming models is infeasible and cannot be deployed. To solve this problem, this work studies the short-term scheduling problem of crude oil operations in a control theory perspective. The system is modeled by a hybrid Petri net and a short-term schedule is seen as a series of control commands. With this model, schedulability analysis is carried out and schedulability conditions are presented. These conditions can be used as constraints for finding a realizable and optimal refining schedule. Moreover, based on the proposed approach, a detailed schedule can be easily obtained given a realizable refining schedule. In this way, the complexity for the short-term scheduling problem of crude oil operations in refinery is greatly reduced and effective techniques and tools for practical applications can be obtained.

There are varieties of constraints for a short-term scheduling problem of crude oil operations in a refinery. These constraints are difficult to model and complicate the short-term scheduling problem. Among them, oil residency time and high fusion point crude oil transportation constraints are the challenging ones. With high setup cost for high fusion point oil transportation, it is desired that the volume of high fusion point oil can be transported as much as possible by a single setup. This may result in late transportation of other types of crude oil, leading to the violation of crude oil residency time constraint. These constraints are ignored by existing methods in the literature. To solve this problem, this paper studies the problem in a control theory perspective by viewing an operation decision in the schedule as a control. With this idea, the system is modeled by a hybrid Petri net. With this model and tank grouping strategy, schedulability analysis is carried out and schedulability conditions are presented with tank charging and discharging costs being taken into consideration. These conditions are necessary for determining a refining schedule and can be used to check whether a target-refining schedule is realizable or not. If so, a feasible detailed schedule for the refining schedule can be easily obtained by creating the operation decisions one by one.

Because of the complexity of a short-term scheduling problem for crude oil operations, some constraints are ignored in modeling the system by the existing approaches, leading to an infeasible solution. To avoid this, the short-term scheduling problem can be studied in control theory perspective by viewing an operation decision in the schedule as a control. With this idea, this paper conducts the schedulability analysis for systems with two and more than two distillers, and the schedulability conditions are presented with the help of Petri net theory. It shows that the number of charging tanks and their capacity, the amount of crude oil of different types in the charging tanks, the oil transportation rate of the pipeline, and the production rate of the system affect the safeness of the system. It also presents the conditions under which the system can reach its maximal production rate. With the safeness conditions and proved results presented in this paper, if a refining schedule is realizable, a feasible detailed schedule for the refining schedule can be easily obtained by creating the operation decisions for the schedule one by one. In the schedule obtained, the starting time of each operation decision can be at any continuous time point, and the schedule is certainly feasible, which overcomes the difficulty faced by techniques that are based on mathematical programming methods.

Because of various constraints, the short-term scheduling of crude oil operations in refinery is very complicated. So far, there is no effective technique and tool. To solve this problem, this paper models the system by a hybrid Petri net and a short-term schedule is seen as a series of control commands. With this model, schedulability analysis of systems with a single distiller is conducted and schedulability conditions are presented. These conditions can be used as constraints for finding a realizable and optimal refining schedule. Moreover, based on the approach presented in this paper, a detailed schedule can be easily obtained for a realizable refining schedule.

This paper addresses a real-life lot-sizing problem which can be considered a single-item dynamic lot-sizing problem with bounded inventory. The particularity is that the demand of a period can be entirely or partially outsourced with an outsourcing cost. The goal is to minimize the total cost of production, setup, inventory holding, and outsourcing. The cost functions are linear but time-varying. We assume that the unit production cost is constant or nonincreasing over time. The problem is shown to be solvable in a strongly polynomial time with a dynamic-programming approach. The proposed algorithm can solve problems of sizes of up to 400 periods in less than 2 ms on a 1.4-GHz Pentium IV processor.

A short-term schedule for oil refinery should arrange all the activities in every detail for the whole scheduling horizon, leading to a complex problem. There lacks efficient techniques and software tools for its solution applicable to industrial oil refinery. Considering that the feasibility of a schedule is essential, this paper studies the feasibility problem from a control perspective. A short-term schedule is composed of a series of operation decisions (ODs), each of which can be seen as a control. When an OD is executed, it transfers the system from one state to another. To guarantee the schedule feasibility, the system should be always be kept in safe states. The system is modeled by a Petri net model that is under control of the ODs. With this model, schedulability conditions for a system with one distiller are presented. These conditions reveal the relationship among the number of charging tanks, the oil transportation flow rate of the pipeline, and the production rate. The conditions are presented in a constructive way. Based on the conditions, when a realizable refining schedule is verified, a detailed short-term schedule is created for practical use.

The feasibility of a schedule is essential to the operation of a complex system involving both discrete and continuous processes. This paper studies the short-term scheduling problem for crude oil operations in a control theory perspective. A short-term schedule is composed of a series of operation decisions, each of which can be seen as control. Their execution transfers the system from one state to another. To guarantee a schedule’s feasibility, the system must always be kept in safe states. It is modeled by a Petri net that is under the control of operation decisions. With this model, safeness or schedulability conditions are presented. They reveal the relationship among the number of charging tanks, oil transportation flow rate of the pipeline, and production rate. Based on them, if a refining schedule is found schedulable, a detailed short-term schedule is created as well.

This paper addresses a real-life single-item dynamic lot sizing problem arising in a refinery for crude oil procurement. It can be considered as a lot sizing problem with bounded inventory. We consider two managerial policies. With one policy, a part of the demand of a period can be backlogged and with the other, a part of the demand of a period can be outsourced. We define actuated inventory bounds and show that any bounded inventory lot sizing model can be transformed into an equivalent model with actuated inventory bounds. The concept of actuated inventory bounds significantly contributes to the complexity reduction. In the studied models, the production capacity can be assumed to be unlimited and the production cost functions to be linear but with fixed charges. The results can be easily extended to piecewise linear concave production cost functions. The goal is to minimize the total cost of production, inventory holding and backlogging, or outsourcing. We show that the backlogging model can be solved in O(T2) time with general concave inventory holding and backlogging cost functions where T is the number of periods in the planning horizon. The complexity is reduced to O(T) when the inventory/backlogging cost functions are linear and there is no speculative motives to hold either inventory or backlogging. When the outsourcing levels are unbounded, we show that the outsourcing model can be transformed into an inventory/backlogging model. As a consequence, the problem can be solved in O(T2) time, if the outsourcing cost functions are linear with fixed charges even if the inventory holding cost functions are general concave functions. When the outsourcing level of a period is bounded from above by the demand of the period, which is the case in many application areas, we show that the outsourcing model can be solved in O(T2logT) time if the inventory holding and the outsourcing cost functions are linear. Note to Practitioners-This paper considers dynamic lot-sizing models with bounded inventory and outsourcing or backlogging decisions. Based on the forecasted requirements of a given item for each period of the planning horizon, the problem consists of determining the quantity to be produced inhouse or to be ordered from a supplier and the quantity to be outsourced in each period to minimize a total cost over the considered planning horizon, composed of the production or purchasing cost, inventory holding cost, and the backlogging cost or the outsourcing cost. These problems initially come from real-life crude oil procurement and often arise in many companies. In this paper, we consider two models. In one model, backlogging is allowed with a backlogging penalty while there is no possibility of outsourcing. In the other model, all of the customer requirements are satisfied in time (i.e., without backlogging) but outsourcing is possible. For each model, we develop an algorithm to find an optimal solution. The computation time of these algorithms can be bounded by a one or two degree polynom of the number of periods in the planning horizon, which means that the computation time required to find an optimal solution is very short

Recently, there has been a great interest in the modeling and analysis of process industry, and various models are proposed for different uses. It is meaningful to have a model to serve as an analytical aid tool in short-term scheduling for oil refinery process. However, in oil refinery process, there are special constraints and requirements, and the existing models cannot be applied directly. Thus, as an application in this paper, we extend the hybrid Petri net to model the crude-oil operations in oil refinery process. This Petri net is called controlled colored timed Petri net (CCTPN). In this model, a token carries both discrete and continuous properties. A token in a discrete place shows its discrete properties, while the continuous properties are captured when it is in a continuous place. A discrete transition treats a token just as a discrete one, and a continuous transition deals with it as a continuous one. In this way, we integrate the discrete and continuous processes together in the CCTPN. Based on the CCTPN, liveness for CCTPN is defined, and with the liveness definition we show how to detect conflicts in scheduling the system by using this model.

In this paper we consider a dynamic lot sizing model with mixed backlogging and outsourcing and bounded inventory, in which outsourcing may occur in a period even if the inventory level at that period is positive. The production cost may include setup cost and the production level is unlimited. The holding, backlogging and outsourcing cost functions are linear. Furthermore, backlogging level at each period is limited, and outsourcing level at each period cannot exceed the demand of that period. The goal is to minimize the total cost of production, inventory holding/backlogging and outsourcing. We show that this problem can be solved in O(T4log T) time where T is the length of the planning horizon. Finally, the proposed algorithm is implemented in C++ and evaluated on a large variety of instances generated randomly.

This paper addresses multi-degree cyclic scheduling of two robots in a no-wait flowshop, where exactly r(r > 1) identical parts with constant processing times enter and leave the production line during each cycle, and transportation of the parts between machines is performed by two robots on parallel tracks. The objective is to minimize the cycle time. The problem is transformed into enumeration of pairs of overlapping moves that cannot be performed by the same robot. This enumeration is accomplished by enumerating intervals for some linear functions of decision variables. The algorithm developed is polynomial in the number of machines for a fixed r, but exponential if r is arbitrary. Computational results with benchmark instances are reported. Note to Practitioners-This paper was motivated by the problem of cyclic scheduling of a no-wait production line, where a part must be processed without any interruption either on or between machines due to characteristics of the processing technology itself or the absences of storage capacity between operations of a part. Multi-degree schedules, in which multiple parts enter and leave the line during a cycle, usually have larger throughput rate than simple ones. This paper proposes an algorithm for multi-degree cyclic scheduling of a no-wait flowshop with two robots. Computational results show that the throughput rate can be really improved by using multi-degree schedules with two robots. However, we have not addressed the decision of the optimal value of the degree of the cycle. Furthermore, since we consider that the two robots travel along parallel tracks, the collision-avoidance constraints have been relaxed in the algorithm. In future research, we will address the two problems and generalize the algorithm to multi-robot cases.

Reliability & redundancy allocation is one of the most frequently encountered problems in system design. This problem is subject to constraints related to the design, such as required structural, physical, and technical characteristics; and the components available in the market. This last constraint implies that system components, and their reliability, must belong to a finite set. For a parallel-series system, we show that the problem can be modeled as an integer linear program, and solved by a decomposition approach. The problem is decomposed into as many sub-problems as subsystems, one sub-problem for each subsystem. The sub-problem for a given subsystem consists of determining the number of components of each type in order to reach a given reliability target with a minimum cost. The global problem consists of determining the reliability target of subsystems. We show that the sub-problems are equivalent to one-dimensional knapsack problems which can be solved in pseudopolynomial time with a dynamic programming approach. We show that the global problem can also be solved by a dynamic programming technique. We also show that the obtained method YCC converges toward an optimal solution.

International audience

This paper considers the allocation of reliability and redundancy to parallel-series systems, while minimizing the cost of the system. It is proven that under usual conditions satisfied by cost functions, a necessary condition for optimal reliability allocation of parallel-series systems is that the reliability of the redundant components of a given subsystem are identical. An optimal algorithm is proposed to solve this optimization problem. This paper proves that the components in each stage of a parallel-series system must have identical reliability, under some nonrestrictive condition on the component's reliability cost functions. This demonstration provides a firm grounding for what many authors have hitherto taken as a working hypothesis. Using this result, an algorithm, ECAY, is proposed for the design of systems with parallel-series architecture, which allows the allocation of both reliability and redundancy to each subsystem for a target reliability for minimizing the system cost. ECAY has the added advantage of allowing the optimal reliability allocation in a very short time. A benchmark is used to compare the ECAY performance to LM-based algorithms. For a given reliability target, ECAY produced the lowest reliability costs and the optimum redundancy levels in the successive reliability allocation for all cases studied, viz, systems of 4, 5, 6, 7, 8, 9 stages or subsystems. Thus ECAY, as compared with LM-based algorithms, yields a less costly reliability allocation within a reasonable computing time on large systems, and optimizes the weight and space-obstruction in system design throughout an optimal redundancy allocation.

Proposes an exact algorithm for the multicyclic schedules of hoist moves in a printed circuit board (PCB) electroplating facility, where exactly r(r>1) parts enter and r parts leave the production line during each cycle, and the processing time at each production stage is a given constant. The multicyclic scheduling problem is transformed into enumeration of intervals for linear functions of decision variables. This enumeration is accomplished with a branch and bound procedure. At each node of the search tree, by solving a linear programming problem (LPP), either the corresponding partial solution is proved to be unable to lead to a feasible solution, or a lower bound is computed. Due to its particular structure, this LPP is equivalent to a cycle time evaluation problem in a bivalued graph which can be solved efficiently. The proposed algorithm is polynomial in the number of tanks for a fixed r, but exponential if r is arbitrary. Computational experience with both benchmark and randomly generated test instances is presented.

We consider single machine scheduling problems in which due dates are assigned according to the CON (common due date) rule. The objective in this problem is to find an optimal value of the due date and the related optimal schedule in order to optimize a given criterion based on the due date and the completion times of jobs.

In this paper we consider a one-dimensional bin packing problem where the bins do not have identical sizes, or a variable-sized bin packing problem, to minimize the bin consumption, i.e., the total size of the opened bins. The identical size problem has been extensively studied in the literature both for static and dynamic settings. The worst-case or average-case performance has been analyzed. Our problem setting particularly arises in metal cutting industries. Therefore, it presents a great practical relevance. Four greedy approximation algorithms based on a construction approach called largest object first with least absolute waste (LFLAW), largest object first with least relative waste (LFLRW), least absolute waste (LAW), and least relative waste (LRW) are examined. Their absolute worst-case performances are analyzed. The worst case bounds are 2 for LFLAW and LFLRW, 3 for LAW, and 2+ln 2 for LRW. We also show that these worst-case bounds are tight.

This paper proposes a model and a related algorithm for generating optimal cyclic schedules of hoist moves with time window constraints in a printed circuit board (PCB) electroplating facility. The algorithm is based on the branch and bound approach and requires the solution of a specific class of linear programming problems (LPP). These LPP are equivalent to the problems of the cycle time evaluation in bi-valued graphs. Computational experience is presented to compare the results obtained using this new algorithm with the ones proposed in the literature.

Concerns the use of Lagrangean relaxation for complex scheduling problems. The technique has been used to obtain near-optimal solutions for single machine and parallel machine problems. It consists of relaxing capacity constraints using Lagrange multipliers. The relaxed problem can be decomposed into independent job level subproblems. Luh et al. (1990, 1991) extended the technique to general job shop scheduling by introducing additional Lagrangean multipliers to relax precedence constraints, so that each job level relaxed subproblem can be further decomposed into a set of operation level subproblems which can easily be solved by enumeration. Unfortunately, the operation level subproblems exhibit solution oscillation from iteration to iteration and, in many cases, prevent convergence. Although several methods to prevent oscillation have been proposed, none is satisfactory. We propose an efficient pseudo-polynomial time dynamic programming algorithm. We show that, by extending the technique to job shop scheduling problems, the relaxation of the precedence constraints becomes unnecessary, and thus the oscillation problem vanishes. This algorithm significantly improves the efficiency of the Lagrangean relaxation approach to job-shop scheduling, and makes it possible to optimize "min-max" criteria by Lagrangean relaxation. These criteria have been neglected in the Lagrangean relaxation literature due to their indecomposability. Computational results are given to demonstrate the improvements due to this algorithm.

We consider a single machine scheduling problem which we studied to improve the efficiency of an automated medical laboratory. In this problem, there are not only chain structured precedence constraints, but also minimal and maximal times separating successive jobs in the same chain (separation time windows). The criterion to be minimized is the makespan. Potential applications are not restricted to medical analysis. This problem often arises in systems where chemical processes are involved. Therefore the problem studied in this paper is important in practice. We prove that the problem is nonpolynomial (NP)-complete. As a consequence, we propose three heuristics for large size problems and a branch and bound based algorithm for small size problems. Computational results are reported.

Lagrangian relaxation consists of relaxing capacity constraints using Lagrangian multipliers and of decomposing the problem into job level subproblems. In the literature, when job shop scheduling problems are considered, these subproblems are further decomposed into operation level subproblems by relaxing precedence constraints. Unfortunately, this results in solution oscillation and often prevents convergence of the algorithm. Although several methods have been proposed to avoid solution oscillation, none of them is really satisfactory. In this paper, we propose an efficient pseudopolynomial time dynamic programming algorithm to solve relaxed job level subproblems. This makes the relaxation of precedence constraints unnecessary. The solution oscillation can then be avoided. This algorithm also results in a much more efficient Lagrangian relaxation approach to job-shop scheduling problems. Computational results on randomly generated problems are given to demonstrate the efficiency of the algorithm.