Exact and Heuristic Algorithms for the Job Shop Scheduling Problem with Earliness and Tardiness Over a Common Due Date

<p>Scheduling has turned out to be a fundamental activity for both production and service organizations. As competitive markets emerge, Just-In-Time (JIT) production has obtained more importance as a way of rapidly responding to continuously changing market forces. Due to their realistic assumptions, job shop production environments have gained much research effort among scheduling researchers. This research develops exact and heuristic methods and algorithms to solve the job shop scheduling problem when the objective is to minimize both earliness and tardiness costs over a common due date. The objective function of minimizing earliness and tardiness costs captures the essence of the JIT approach in job shops. A dynamic programming procedure is developed to solve smaller instances of the problem, and a Multi-Agent Systems approach is developed and implemented to solve the problem for larger instances since this problem is known to be NP-Hard in a strong sense. A combinational auction-based approach using a Mixed-Integer Linear Programming (MILP) model to construct and evaluate the bids is proposed. The results showed that the proposed combinational auction-based algorithm is able to find optimal solutions for problems that are balanced in processing times across machines. A price discrimination process is successfully implemented to deal with unbalanced problems. The exact and heuristic procedures developed in this research are the first steps to create a structured approach to handle this problem and as a result, a set of benchmark problems will be available to the scheduling research community.</p>

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Engineering Management & Systems Engineering

Year dc:date.available

2007

Author dc:creator

• Bedoya-Valencia, Leonardo

Contributors dc:contributor

• Ghaith Rabadi
• Andres Sousa-Poza
• Resit Unal
• Ali Ardalan

• Common due date
• Earliness
• Job shop scheduling
• Scheduling
• Tardiness
• Industrial Engineering
• Operational Research

Identifier

9780549320463

OAI identifier oai:identifier

oai:digitalcommons.odu.edu:emse_etds-1046