Scheduling Hazardous Waste Incinerators Using a Simulated Annealing Linear Programming Heuristic

Abstract

This article presents an algorithm for scheduling waste feeds for a hazardous waste incinerator based on a simulated annealing linear programming heuristic. The originality of the formulation and solution procedure of the incinerator scheduling problem lies in the large number and type of utility constraints used to model permit and other limits. The algorithm is effective on large scheduling problems with 200 jobs and 10 feed points. Computational experiments suggest that the incinerator scheduling problem is easier to solve to a lower bound for a makespan objective if the permit limits are more restrictive than the individual feed point limits. To aid in understanding the schedule produced, the scheduling problem is repetitively solved to determine the variation in alternative schedules. This unique analysis demonstrates that multiple solutions to the scheduling problem exist with similar makespans. These alternative solutions are due to the tightness of the permit limit constraints for this problem and the makespan objective. The article suggests several secondary objectives to generate a unique solution. The proposed algorithm can be utilized by incinerator operators to improve efficiency.

Introduction

Hazardous waste incinerators destroy materials that are hazardous to the environment and human health. The high-temperature combustion chamber converts wastes into nontoxic materials such as carbon dioxide, water, and inorganic slag, which is stable and safe to landfill. The operating challenge of a hazardous waste combustor (HWC) is to effectively schedule the waste streams within permit limits. In the United States, HWCs are permitted by the Environmental Protection Agency (EPA) and state environmental agencies under the National Emission Standards for Hazardous Air Pollutants for Source Categories codified in the federal registry (National Archives and Records Administration, 2006). Permit limitations place minimum and maximum bounds on the concentration or total mass of toxic constituents in the waste feed streams. Permits also have limits based on total feed rates and total heat content being fed to the unit at any given time. Given the negative consequences of exceeding physical or permit limits, incinerators typically have conservative operating limits set below the permit or physical limits. The most restrictive of the permit, operational, and physical limitations define an operating window for the facility.

This article explores scheduling parallel feed points in a rotary kiln hazardous waste incinerator. The schedule is restricted by emission and operational limits for multiple chemical components, heat limits, and flow rate limits at feed points. The goal of the scheduling algorithm is to minimize the makespan, the time required to dispose all on hand waste. An optimal schedule for makespan will complete all jobs in a minimum amount of time. Scheduling a hazardous waste incinerator is a challenging task. A schedule must consider multiple permit and physical limits when designing a schedule that sets the flow rates, feed point assignments, and job sequence. The schedule must also map the inputs in the waste stream into resulting outputs from the unit. A large incinerator can have over 15 component limits, 10 or more feed points with mass flow limits, and a large number of jobs waiting to be processed.

This article studies a semibatch process in that the flow rates are continuous and each job has a defined start and completion time. The completion time for a job is reached when the contents of a trailer or tank are burned out. Jobs are typically not interrupted during the burn period, but the flow rates can be modified based on the jobs currently running. This problem requires that the scheduler set the next job and flow rates for all feed points when a job completes processing in the schedule. To construct a full schedule, a large number of decisions must be made by the scheduler, including the defining sequences of jobs and flow rates for all running jobs that can change when any job completes processing. Because of the large number of decisions and permit limit constraints, an algorithm to aid the decision process is beneficial.

This research employs a simulated annealing linear programming (SA-LP) heuristic to solve the scheduling problem. The SA component determines the sequence of the jobs for waste feeds to the incinerator, and the linear programming component sets the flow rates and determines the makespan and other objectives. An SA-LP heuristic approach was chosen because of the complexity of the problem. This SA-LP approach is similar to the approach used by prior researchers who used SA-LP to decompose chemical scheduling problems (Cardoso et al., 1997; Xi-Gang and Zhong-Zhou, 1997; An and Yuan, 2009). He and Hui (2008) employed a similar decomposition using genetic algorithms instead of SA for scheduling parallel machine in a chemical manufacturing facility. The importance of permit and other limits across multiple feed points in incinerator operations creates a unique scheduling environment.

The incinerator scheduling problem is a semibatch process with parallel machines problem. A common assumption in machine scheduling literature is the independence of the machines being scheduled. In the incinerator scheduling problem, permit and operational constraints based on emissions and heat content limits generate utility constraints across machines. In a more traditional chemical scheduling environment, utility constraints would typically include electricity, steam, cooling water, and other shared feeds. Behdani et al. (2007) presented a demonstration of the importance of utility constraints in chemical scheduling models. Without the utility constraints, the optimal schedule tightly packs jobs together. The utility constraints that limit the concurrent processing of jobs result in a schedule that spaces out the jobs by making run times longer and resequencing tasks. Their model was demonstrated on small problems where optimal solution procedures could be employed. The utility constraints separate this scheduling problem from a traditional machine scheduling problem by making the processing time of jobs dependent on the other running jobs and their flow rates.

If a schedule is constrained by a single utility constraint, our computational results demonstrate that a large number of solutions might be optimal or near optimal for a makespan objective. The algorithm designer should be aware that the sequence positions and machine assignments might not be uniquely specified by the formulation. If a formulation does not specify a single solution, then a user might be able to construct a schedule with the same cost but with improved performance for secondary criteria. If a user is able to construct a schedule that is better from the secondary criteria perspective, than the schedule developed by the scheduling system, the system would lose credibility with the end user. This loss of credibility would be difficult to recover during the scheduling system implementation. As a result, developers of scheduling systems should measure if their formulations generate a unique solution to avoid the potential of a user developing a better schedule. If the formulation does not uniquely identify a schedule, practitioners should consider adding additional objectives and constraints until a unique schedule is identified.

This article is organized as follows: section “Problem Background” provides background on the problem and describes a schedule for a hazardous waste incinerator. Section “SA-LP Heuristic” presents the SA-LP algorithm used to solve the incinerator scheduling problem. Section “Computational Results” presents computational results on the effectiveness of the algorithm. Section “Conclusions” discusses conclusions and presents future research directions.

Problem Background

Limited research has been performed on scheduling hazardous waste incineration because of a relatively small installation base. Perdek (1997) discussed the importance of accurate waste characterization when bidding hazardous waste incinerator services. Considerable research exists on the chemical issues related to incinerators, such as Chow et al. (2008), but limited research has been performed on scheduling incinerators. As of January 1997, there were only 156 permitted (commercial and industrial) hazardous waste incinerators in the United States at 110 locations (Reynolds et al., 2000).

Hazardous waste incinerators are an important way to destroy materials that are hazardous to the environment and human health. The high-temperature combustion chamber can convert wastes into nontoxic materials such as carbon dioxide, water, and inorganic slag, which is stable and safe to landfill. An operating challenge for an HWC is the wide range of wastes commonly disposed at chemical incinerators. HWCs are permitted by the EPA (2006) and state environmental agencies under the National Emission Standards for Hazardous Air Pollutants for Source Categories codified in the federal registry. Permits usually have limits on variables such as concentration or total amount of toxic constituents in the waste feed streams. Permits also have limits based on total feed rates and total heat content being fed to the unit at any given time. In addition to permit limits, incinerators have physical and operational limits. The most restrictive of permit, operational, and physical limits define an operating window for an incinerator unit.

The schedule for an incinerator sets the flow rates and jobs assigned to each feed point. The schedule can be modeled as a series of recipes that specify the jobs running at a given point in time. A recipe's duration is defined by the time interval between two job completions. Each recipe completion time corresponds to a job completing and starting a different job on the feed point. Each recipe specifies the job operating on the feed point and the flow rates of those jobs. Using this information, the output chemical components and heat from the incinerator is computed based on the input material. The problem is formulated as a continuous time parallel machine scheduling formulation. Each job represents a type of waste being fed from a tank or directly burned from a trailer. Each feed point on the incinerator acts as a separate machine. In this system, each feed point is fed from only one tank. Each feed point (machine) can process only one job at a time. The waste in a given tank, drum, or trailer is assumed to be homogeneous. Based on the problem structure, the flow rates through each feed point during a recipe will remain constant. When a new recipe starts, the flow rates on all feed points can change. The research assumes that jobs are not preempted and flow rates remain constant during the period covered by a recipe. This assumption is valid for typical incinerator operations.

Figure 1 shows a simple illustration of an incinerator schedule. The Gantt chart displays the schedule in a series of recipe blocks defined by the same set of jobs running on the feed points. The Gantt chart shows the start time and the end time of recipes in the first two rows. The next “M” rows specify what job is run in each feed point and the flow rate of the jobs. The final set of “Q” rows of the table presents the utilization of component limits and feed point limits. The limits include kilogram per hour or concentration of components such as chlorine, fluorine, sulfur, mercury, and others. Limits also include enthalpy heat feed rate and feed rate in kilogram per hour for the system total, segments of the incinerator, and individual feed points. A typical incinerator will have many limits that must be displayed to the scheduler. Keeping this information in a single workspace is an effective method for displaying the information in the schedule. In the software developed in this research project, red background indicates components that are within 90%–100% of the limit and green background components are those between 50% and 90% of the limit. In Fig. 1, the color coding is illustrated with gray shading. The color coding provides the scheduler with an indication where the bottlenecks are occurring and alerts them to components that are near the limit in the schedule. An effective schedule display is critical to gain user acceptance of a scheduling system.

FIG. 1.

Illustration of an output schedule for an incinerator scheduling algorithm.

SA-LP Heuristic

Because of the large number of variables, this scheduling problem is decomposed into assigning jobs to machines and sequence positions and then setting the flow rates based on the machine assignments and sequences. An SA heuristic sets the machine assignment and completion sequence. The completion sequence specifies the order that jobs complete processing. This information is passed to the linear program that sets the flow rates to minimize the makespan given the specified sequence positions and machine assignments. This style of decomposition is common in chemical scheduling literature (Cardoso et al., 1997; Xi-Gang and Zhong-Zhou, 1997; An and Yuan, 2009), but the incinerator scheduling problem is unique because of the importance of permit limits modeled as utility constraints.

Sequencing with SA

Simulated annealing is a common meta-heuristic for scheduling. Simulated annealing for combinatorial optimization was first introduced by Kirkpatrick et al. (1983). Pinedo (1995) provides a good background reference for using SA for machine scheduling. The scheduling algorithm employs SA to construct a partial schedule that specifies the machine assignments and completion sequence. The linear program completes the partial schedule by setting the flow rates. The steps of the SA heuristic are as follows:

Generate an initial partial schedule by randomly setting the completion sequence for jobs and randomly assigning the jobs to machines. Calculate the flow rates and cost of the initial partial schedule using linear programming (see section “LP formulation to set flow rates”). Set the number of iteration to zero, i = 0.

Generate a new partial schedule from the current schedule using neighborhood search and calculate its cost by setting flow rates using the linear programming. The neighborhood search employed to generate subsequent schedules is based on interchanging two jobs or moving a single job to a random position and machine. To interchange two jobs, the machine assignment and completion positions of the two randomly selected jobs are exchanged. To move a single job, the job is removed from the completion sequence and reinserted into a random position on a random machine.

If the new schedule is an improvement over the prior schedule based on the LP evaluation in the section “LP formulation to set flow rates,” set the schedule for the next iteration to the new schedule.

If the new schedule is worse than the prior schedule, probabilistically accept the schedule for the next iteration. The probability of accepting the worse schedule is e^(−Δ/Ti), where Δ is the difference in schedule cost and T_i is a temperature at iteration i that controls the acceptance probability. If the schedule is rejected, undo the changes to the schedule made in step 2. A cooling schedule allows worse schedules to be accepted with greater probability at the start of the search than at the end of the search. A geometric cooling schedule is employed in this research to reduce the temperature where T_i+₁ = (1 − α)T_i, where α is the cooling rate.

If the new schedule is the best schedule found, record the schedule.

Increment the number of iterations, i = i + 1.

If the number of iterations equals the maximum number of iterations, record the best schedule for the SA-LP replication, else go to step 2.

By running multiple independent replications of the SA-LP algorithm, this research generates multiple candidate schedules. These candidate schedules are analyzed to determine if the formulation generates a unique solution to the scheduling problem.

LP formulation to set flow rates

The schedule produced by the SA portion of the algorithm assigns each job to a machine in a given sequence completion position without setting the flow rate. The completion sequence and machine assignments are sent to the linear programming portion of the algorithm to determine the flow rates and makespan. During each iteration, a linear program is constructed and solved.

The primary goal of incinerator scheduling is to minimize the amount of time required to complete all the jobs. As such, the objective of the scheduling algorithm is to minimize the makespan for completing all jobs (Equation 1) where C_max is the completion time of the last recipe. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}\begin{align*}{\rm min} C_{\rm max} \tag {1}\end{align*}\end{document}

The limits are modeled as a series of constraints. These limits restrict the number of kilogram per hour of chemical components including chlorine, fluorine, sulfur, mercury, and others. Limits also restrict the enthalpy heat fed to the unit per hour. For these limits, the most restrictive of the permit limit and the operation limit should be selected for the system limit. The completion time of each recipe C_r corresponds to completing a job in the schedule and starting a new job on a feed point. Let x_r,j be the amount of job j ∈ {jobs} in kg run in recipe r ∈ {recipes}, L_i be limit of component i ∈ {limits}, and a_j,i be the fraction of component i in job j. The component limits include limits on individual chemical components, heat, and mass for the entire incinerator unit. Let jobs_r be the set of jobs running in recipe r and recipes_j be the set of recipes that contain job j. The jobs run in each recipe are specified by the SA algorithm that sets the machine assignment and completion positions. Limits on the rate of each component being fed to the unit are represented by Equation 2. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}\begin{align*}C_r - C_{r - 1} \ge \frac {{\sum \limits_{j \in jobs_r}} a_{j, i} x_{r, j}} {L_i} \ \hbox {for all} \ r \in \{recipes\}, i \in \{limits\} \tag {2}\end{align*}\end{document}

The individual machines also have flow and heat limits (Equation 3) where L_r,j is the limit on flow based on the feed point restrictions. L_r,j is a constant for the feed point-specific restrictions for job j in recipe r based on the feed point (machine) assignments and completion sequence assignments from the SA heuristics. Each feed point can have limits for heat and mass flow where L_r,j is the maximum flow rate for the job based on the feed point limits. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}\begin{align*}C_r - C_{r - 1} \ge \frac {x_{r, j}} {L_{r, j}} \ \hbox {for all} \ r \in \{recipes \},j \in \{jobs_j\} \tag {3}\end{align*}\end{document}

In some incinerator environments, sections of the unit can have limits for heat and component amounts. These limits are modeled similar to Equation 2 except the limit applies to a subset of jobs based on the scheduled constructed from the SA algorithm.

All jobs must be completed (Equation 4) where Q_j is the total amount of waste job j in kg. The set recipes_j specifies the recipes where job j is run based on the assignments in the SA heuristic. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}\begin{align*}\sum \limits_{r \in \{recipes_j\}} x_{r, j} \ge Q_j \ \hbox {for all} \ j \in \{jobs\} \tag {4}\end{align*}\end{document}

The bounds for the problem are that flow rates be positive (Equation 5) and the time starts at zero (Equation 6). \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}\begin{align*}x_{r, j} \ge 0 \ \hbox {for all} \ r \in \{recipes_j\}, j \in \{jobs\} \tag {5}\end{align*}\end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}\begin{align*}C_{\rm o} = 0 \tag {6}\end{align*}\end{document}

For the makespan objective, a lower bound can be constructed based on the utility constraints and the machine flow rate limits. The lower bound is calculated based on dividing the amount of waste of each component by the limit for each component (Equation 7). For the feed point specific limits, a total amount for the limit for the unit is used to construct a bound. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}\begin{align*}C_{\max} \ge {\rm max}_{i \in limits} \frac {\sum \limits_{j \in \{jobs\}} Q_j a_{i, j}} {L_i} \tag {7}\end{align*}\end{document}

This decomposition leads to a flexible formulation that can support weighted average completion time (Equation 8) where w_r is the weight of the job that completes processing in recipe r. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}\begin{align*}{\rm min} \sum \limits_{r \in \{recipes\}} w_rC_r \tag{8}\end{align*}\end{document}

The constraints are the same as the average completion time in the prior section.

The algorithm was implemented in Microsoft Visual C + + ™ with COIN-OR CLP™ employed to solve the linear program. Microsoft Access™ was employed to store the problem and output schedules. See Lougee-Heimer (2003) for more information on COIN-OR and the advantages of open source software in research, including documentation of implementation details, reproducibility of results, and reuse.

Computational Results

The algorithm was tested on generated problems developed from the waste composition streams and limits of a commercial incinerator. The results of the computational test demonstrate the algorithm was capable of solving commercial size scheduling problems. Given the size of the scheduling problem and the large number of utility constraints, the ease of solving these instances was surprising. The actual incinerator problem was not difficult because of global operational and permit limits being more restrictive than the flow rate limits on individual feed points. A single utility constraint limiting a parallel process is not uncommon in chemical scheduling. Because of business confidentiality considerations, this article generates generic problems inspired by the commercial incinerator studied. These generated problems test the effectiveness of the algorithm and illustrate the importance of utility constraints on the effectiveness of the algorithm and the lower bound for makespan.

This article presents computational results for a series of problems with multiple utility constraints that are similar to those found in the case study incinerator. A permit limit of 100 kg/h was set for all components. The fraction of components in the waste stream was distributed as Uniform[0, 0.025] for component 1, Uniform[0, 0.015] for component 2, Uniform[0, 0.01] for component 3, Uniform[0, 0.01] for component 4, and Uniform[0, 0.005] for components 4–10. For the 10-machine problems, the flow rate limits for the individual feed points were set to 1,000 kg/h. For the five machine problems, the flow rates on the individual feed points were set to 2,000 kg/h to keep the relative importance of the utility constraints for components constant. Based on the problem construction settings, component 1 will typically set the makespan. The algorithm was run for 20,000 iteration. The initial temperature for the SA was set to 0.05, with a geometric cooling rate of 0.001. For neighborhood search, the probability of moving a single job was 0.5 and the probability of swapping two jobs was set at 0.5.

The results demonstrate that this problem can be solved relatively quickly to the lower bound (Equation 7) with SA (Table 1). Table 1 displays the average run time, run time per iteration, fraction of problems solved to the lower bound (Equation 7), and maximum gap between the lower bound and schedule found with our heuristic for 10 problems constructed for each problem size. The run time increased with the number of machines and the number of jobs. The algorithm was able to reach the lower bound for all instances except for one instance of 200 jobs 10 machines. In this case, the gap between the lower bound and the schedule found was 0.12 min and inconsequential from a practical standpoint. The run time for the algorithm was about 30 min for the 10 machines 50 jobs' problems. This run time is reasonable for an incinerator scheduling problem designed to run once per day. The algorithm was effective for this constructed environment that is similar to the environment that motivated this study. All problems were run on a Dell Precision T7400 with 3 GB of RAM with a single thread program.

Table 1.

Computational Results for a Makespan Objective

Jobs	Machines	Average run time (s)	Run time per iteration (s)	Solved to lower bound	Iterations to lower bound	Maximum gap (min)
50	10	1,768	0.08	10/10	11,237	0
100	10	5,586	0.28	10/10	12,919	0
150	10	9,765	0.49	10/10	11,083	0
200	10	15,416	0.77	9/10	14,367	0.12
50	5	809	0.40	10/10	9,878	0
100	5	1,782	0.09	10/10	12,760	0
150	5	3,139	0.16	10/10	11,936	0
200	5	4,358	0.22	10/10	10,395	0

To explore the impact of utility constraints, a series of problems was generated with a single utility constraint. For these problems, the mass of the jobs was distributed as Uniform[0, 20,000]. The generated problems have 10 feed points that can each process 1,000 kg/h. A permit limit of 100 kg/h was set for a permit utility constraint. The fraction of this component in the jobs was varied from Uniform[0,0.03] (kg/kg), representing a problem dominated by the utility constraint, to Uniform[0, 0.01], representing a problem dominated by the feed point flow rate restrictions. A problem without utility constraints was also run for comparison purposes. Ten problems were constructed and solved with the SA-LP algorithm for each distribution of components. The settings for the SA-LP algorithm were 10,000 iterations, 0.05 initial temperature, and a geometric cooling rate of 0.001. The results demonstrate that problems where the utility constraint dominates the individual feed point constraints are easily solved to the lower bound given in Equation 7 (Table 2). The problems where the utility constraint does not dominate were not solved to the lower bound. This result is due to the decreased effectiveness of both the algorithm and the lower bound when the makespan is not set by the utility constraint. This result highlights how a tight utility constraint can make the parallel machine scheduling problem computationally easier.

Table 2.

Fifty Jobs 10 Machines' Problems with Different Component Concentrations

Problem set	Component concentration distribution	Ratio of utility constraint to flow restriction	Average gap (%)	Problems solved to lower bound
1	Uniform[0, 0.025]	1.125	0.0	10/10
2	Uniform[0, 0.02]	1.000	0.8	4/10
3	Uniform[0, 0.15]	0.750	1.6	0/10
4	Uniform[0, 0.01]	0.500	1.8	0/10
5	No utility constraint	0.000	1.4	0/10
6	Typical incinerator	1.25	0.0	10/10

Developing a formulation that specifies all decision variables should be a goal of a formulation exercise. If a formulation has an excessive number of alternative optimal and near optimal solutions, then a user might be able to construct a solution that is perceived to be better than the solution proposed by the optimization system. To test for alternative optimal solutions, the prior scheduling problems are solved repetitively and the results are stored. One instance of the 100 jobs 10 machines' problems in Table 1 was resolved 25 times to determine if the formulation specified a unique assignment of jobs to machines. All 25 solutions to the same problem instance found a different schedule without clear patterns for machine assignment or completion time. This result is not unexpected because of the makespan objective, but it does suggest that users must consider additional factors to specify a unique schedule. Unlike traditional scheduling environments where tardiness, average completion time, and earliness are the primary scheduling considerations, incinerators are primarily scheduled to maximize throughput by minimizing makespan. With this simple objective, a large number of alternative schedules might satisfy the scheduler's goals in environments constrained by permit limits instead of flow rate restrictions.

To use the flexibility in the scheduling environment, a user should consider adding additional scheduling objectives beyond makespan. One additional objective to help identify a unique schedule is to minimize schedule nervousness. Nervousness occurs when the schedule produced by the algorithm unnecessarily changes machine assignments, flow rates, completion times or start times without improving the scheduling objective. Curry and Peters (2005) describes the problems associated with nervous schedules including potential operator confusion, coordination of supporting activities, and difficulty reviewing the new schedule. If the new schedule is materially different than the old schedule, a scheduler will require more time to review and validate the schedule. In incineration scheduling, the time required to review schedule changes is important because of the critical requirements of permit limits. A penalty for changing machine assignments or completion positions can be added to the objective of the formulation without changing the decomposition of the problem to control nervousness.

Another additional objective to aid in identifying a unique schedule is to penalize the schedule for approaching limits that do not set the makespan. For components that do not set the makespan, one should not construct a schedule that is near the limit of the component because heterogeneity in the inputs can lead to some fluctuating output streams. Establishing operational limits is challenging in an incinerator scheduling environment because of the negative consequences of exceeding limits, including unit shutdown and permit violations. Because of the negative consequences, operational limits are typically conservative, and determining appropriate operational limits is a challenging part of scheduling system implementation.

In some environments, minimizing the use of natural gas by maintaining adequate heat content in the input waste feeds might also be a secondary objective to consider. Operational considerations including maintaining constant flow rates for in-process jobs and spacing out job completions in the schedule might also be considered. Discussing these considerations with system users should be part of the implementation of an incinerator scheduling system.

Conclusions

The SA-LP algorithm developed in this research project was successful in generating a schedule that minimizes makespan for a hazardous waste incinerator. For the industrial incinerator studied, the algorithm was able to construct schedules that minimized makespan. Being able to find a schedule with a makespan equal to the lower bound is partially due to the plant being limited by a single utility constraint based on a permit limit for total emissions from the unit. This utility constraint reduces the importance of partitioning jobs to machines in the parallel machine scheduling problem. Computational experiments demonstrated that having a single utility constraint can generate a large number of optimal and near optimal solutions for the parallel machine scheduling problem with a makespan objective. To generate a unique schedule, practitioners should consider adding secondary objectives to the scheduling formulation until only a single optimal schedule is produced by the algorithm.

Future research should explore scheduling in other areas of waste disposal operations. Permit limit and other domain specific constraints generate a unique and rich scheduling environment. One future research direction is to examine a formulation where a job has a random composition or a composition that changes while the job is running because of settling in storage. Modeling the entire waste disposal chain in a supply chain planning approach is also an area for future study. Coordinating the incinerator schedule with transportation planning could reduce costs by limiting demurrage charges for equipment. Another area for future research is the development of tools for editing and modifying incinerator schedules. Developing effective tools is challenging because of the large number of variables that must be edited and reoptimized to make a user-specified schedule change. Determining the variables set by the optimization as opposed to set by the user in manual rescheduling is an important decision. Developing an interface that allows the schedule to set some variables such as sequence position but automates flow rate calculations requires a unique user interface.

References

W.-Z.

, Yuan

X.-G.

2009. A simulated annealing-based approach to the optimal synthesis of heat-integrated distillation sequences. Comput. Chem. Eng., 33:199.

Behdani

, Pishvaie

M.R.

, Rashtchian

2007. Optimal scheduling of mixed batch and continuous processes incorporating utility aspects. Chem. Eng. Process., 46:271.

Cardoso

M.F.

, Salcedo

R.L.

, Feyo de Azevedo

, Barbosa

1997. A simulated annealing approach to the solution of minlp problems. Comput. Chem. Eng., 21:1349.

Chow

J.-D.

, Chai

W.-L.

, Yeh

C.-M.

, Chuang

F.-S.

2008. Recycling and application characteristics of fly ash from municipal solid waste incinerator blended with polyurethane foam. Environ. Eng. Sci., 25:461.

Curry

, Peters

B.A.

2005. Rescheduling parallel machines with stepwise increasing tardiness and machine assignment stability objectives. Int. J. Prod. Res., 43:3231.

, Hui

C.-W.

2008. A rule-based genetic algorithm for the scheduling of single-stage multi-product batch plants with parallel units. Comput. Chem. Eng., 32:3067.

Kirkpatrick

, Gelatt

C.D.

, Vechi

M.P.

1983. Optimization by simulated annealing. Science, 220:671.

Lougee-Heimer

2003. The common optimization interface for operations research. IBM J. Res. Dev., 47:57.

National Archives and Records Administration. 2006. National Emission Standards for Hazardous Air Pollutants for Source CategoriesCode of Federal Regulations Title 40. Pt. 63.12092006. College Park, MD.

10.

Perdek

1997. Decision analysis of incineration costs in superfund site remediation. Environ. Eng. Sci., 14:15.

11.

Pinedo

1995. Scheduling Theory Algorithms and Systems. Upper Saddle River, NJ: Prentice Hall.

12.

Reynolds

J.P.

, Santoleri

J.J.

, Theodore

2000. Introduction to Hazardous Waste Incineration, 2nd. New York: John Wiley & Sons, Inc.

13.

Xi-Gang

, Zhong-Zhou

1997. A hybrid global optimization method for design of batch chemical processes. Comput. Chem. Eng., 21:5685.