Summary of Research

 

                Dr. Zhang’s research is in the field of mathematical programming and optimization, especially linear and integer programming and its applications in Manufacturing and Service Operations, Logistics, Transportation and Engineering Optimization. Some specific projects that Dr. Zhang has worked or is working on are listed as follows.

 

1)      US Postal Equipment and Staff Scheduling (Chief Developer)

U.S.P.S. is the second largest employer in the U.S. with over 800,000 personnel.  More than 1/3 of these employees work at around 275 mail processing centers nationwide.  The central problem here is how to run these facilities efficiently with minimum labor cost.  The problem is modeled as a mixed flow shop and job shop problem with multiple criteria and is solved sequentially.  The core of this optimization scheme is the inclusion of a surrogate constraint in the form of worker shifts that must cover daily labor costs. The inclusion of this constraint is vital and provides a way to combine equipment and labor scheduling.  Several computational improvements, including pre-processing, the use of target solution and decomposition have been elegantly combined to find high quality solutions efficiently.  A decision support system is developed and is now being tested at several facilities.  It is estimated that annual savings on the order of $1.6 million can be achieved per facility (there are 275 facilities nationwide).  The system is expected to be fully deployed in the next three years.

2)      Crew Management in Airline Irregular Operations (One of the Key Developers)

An airline schedule rarely operates as planned due to various disruptions.  These disruptions, if not managed quickly and correctly, could propagate and amplify through the system.  In this project, we investigated how to quickly bring the crew back to their published schedule.  The basic problem was modelled as a set covering with side constraints and variations were investigated to allow robust schedule.  Several algorithms including simulated annealing and Tabu search heuristics, customized branching together adaptive improving techniques were developed to achieve faster convergence.  I assisted with the implementation in Northwest Airlines.  The project was later awarded the Franz Edelman Prize from INFORMS in 2002.

3)      Advertising Allocation for TV Networks (Chief Developer)

Television networks depend on selling a limited number of advertisement slots in their entertainment programs to advertisers to sustain their operations and to deliver programs to homes free of charge.  The problem here is how to efficiently allocate these slots to achieve maximum profits and to meet the advertisers’ demographic coverage requirements.  A two-step hierarchical approach, composed of a winner selection problem and a pod adjustment problem, was designed.  The winner selection problem was then solved using an efficient column generation-based algorithm.  The methodology is applicable to similar advertising allocation problems in other areas, such as cable networks and radio stations.

4)      Design and Optimization of LFSR Based VLSI Testing Structure (Chief Developer)

Testing of digital circuits includes performing test pattern generation and output analysis and is a major portion of the effort in the design, production and usage.  One of a major scheme in VLSI testing is to perform test pattern generation and output response analysis through built-in hardware such as Linear feedback shift registers (LFSR). This research investigates the mathematical model and methodologies to the structure design and optimization of 2D LFSR based VLSI Built-in Self-Test.  Preliminary results show that hardware reduction nearly 80% was achieved -- the optimal size of the testing hardware is only 1/6 as that used reported in the literature.  This research, coupled with the study of test relaxation technique, will provide a novel and direct route to the design of VLSI system with high fault coverage and is expected to reduce testing hardware by orders of magnitudes.

5)      Novel Neighborhood Search for Integer Program with Multiple Solutions (Chief Developer)

Integer programs arise in a variety of engineering and management areas in manufacturing, logistics and supply chain. Though there have been tremendous advances in computational power and discrete optimization solution techniques, integer program remains one of the hardest problems to solve. Most advanced algorithms require deep knowledge and understanding of problem-specific structures for efficient execution, are applicable mostly to 0-1 integer programs, but not well suited for use as a generic solver for a variety of integer programs, or integer programs with general integer variables. This research is to develop an advanced solution methodology for general integer programs through the definition and use of an innovative neighborhood search.  It studies the mechanisms that enable a systematic traversal of the integer program solution landscape and derive their critical properties in covering the solution landscape, as well as efficient forms of neighborhood structures for general integer programs and assess their theoretical and practical properties.  Preliminary results for benchmark test sets such as knapsack and set covering, and practical applications such as airline and postal staff scheduling have suggested the algorithm is computational efficient and is able to obtain multiple solutions with fast convergence than the state of art commercial solver.

 

Research Funds

  •       Rittal Corporation, “Raw Material Warehouse Management : Warehouse-within-Warehouse Identification and Location, Fast/Medium/Slow Mover Identification, Warehouse Layout, and Order Picking Route Optimization to Increase Warehouse Operation Efficiency ”,  $15,000, PI, 08/1/2006 ~ 12/15/2006

  •       Rittal Corporation, “Raw Material Availability, Forecasting, and Inventory Policies Analysis”,  $23,326, PI, 02/01/2006 ~ 05/31/2006

  •      The Wright Brothers Institute Inc., “Wright Innovation and Collaboration (WICC) Virtual Hub”, CO-PI. (PI: Dr. S. Narayanan) $122,000, 10/01/06~09/30/07

  •      The Wright Brothers Institute Inc., “Support for Wright Innovation and Collaboration (WICC) Workshop”, CO-PI. (PI: Dr. S. Narayanan) $53,550, 08/24/06~09/30/07

  •       “A Quick, Effective Neighborhood Search for Integer Programs and Its Applications in Defense Logistics, Supply Chain Management, and Airline Scheduling Problems,” Research Challenge Grant, Wright State University, Principal Investigator, January,2006 ~ December 2006, $14,000

  •      “Mathematical Model and Solution Approaches to the Systematic Design of Linear Feedback Shift Register with Embedded Test Patterns for BIST,” Research Initiation Grant, Wright State University, Principal Investigator, June, 2005  ~ June 2006, $10,000

  •      “Integrated Production Planning and Workforce Scheduling In Processing Industries,” Research Challenge Grant, Wright State University, Principal Investigator, January,2005  ~ December, 2005, $12,000

  •      “An Investigation of Mathematical Programming Techniques to Solve Large Scale Optimization Problems”, Research Challenge Grant, Wright State University, Principal Investigator, August 2003 ~August, 2005, $25,000