Shop scheduling, sequence dependent setups, incompatible job families, batching


The motivation of this research investigation stems from a particular job shop production environment at a large international communications and information technology company in which electro-mechanical assemblies (EMAs) are produced. The production environment of the EMAs includes the continuous arrivals of the EMAs (generally called jobs), with distinct due dates, degrees of importance and routing sequences through the production workstations, to the job shop. Jobs are processed in batches at the workstations, and there are incompatible families of jobs, where jobs from different product families cannot be processed together in the same batch. In addition, there are sequence-dependent setups between batches at the workstations. Most importantly, it is imperative that all product deliveries arrive on time to their customers (internal and external) within their respective delivery time windows. Delivery is allowed outside a time window, but at the expense of a penalty. Completing a job and delivering the job before the start of its respective time window results in a penalty, i.e., inventory holding cost. Delivering a job after its respective time window also results in a penalty, i.e., delay cost or emergency shipping cost. This presents a unique scheduling problem where an earlinesstardiness composite objective is considered. This research approaches this scheduling problem by decomposing this complex job shop scheduling environment into bottleneck and non-bottleneck resources, with the primary focus on effectively scheduling the bottleneck resource. Specifically, the problem of scheduling jobs with unique due dates on a single workstation under the conditions of batching, sequence-dependent iii setups, incompatible job families in order to minimize weighted earliness and tardiness is formulated as an integer linear program. This scheduling problem, even in its simplest form, is NP-Hard, where no polynomial-time algorithm exists to solve this problem to optimality, especially as the number of jobs increases. As a result, the computational time to arrive at optimal solutions is not of practical use in industrial settings, where production scheduling decisions need to be made quickly. Therefore, this research explores and proposes new heuristic algorithms to solve this unique scheduling problem. The heuristics use order review and release strategies in combination with priority dispatching rules, which is a popular and more commonly-used class of scheduling algorithms in real-world industrial settings. A computational study is conducted to assess the quality of the solutions generated by the proposed heuristics. The computational results show that, in general, the proposed heuristics produce solutions that are competitive to the optimal solutions, yet in a fraction of the time. The results also show that the proposed heuristics are superior in quality to a set of benchmark algorithms within this same class of heuristics


If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at

Graduation Date





Geiger, Christopher


Doctor of Philosophy (Ph.D.)


College of Engineering and Computer Science


Industrial Engineering and Management Systems

Degree Program

Industrial Engineering








Release Date

May 2014

Length of Campus-only Access


Access Status

Doctoral Dissertation (Open Access)


Dissertations, Academic -- Engineering and Computer Science, Engineering and Computer Science -- Dissertations, Academic