Heuristics for job shop scheduling problems with progressive weighted tardiness penalties and inter-machine overlapping sequence-dependent setup times | |
| Author | Chatpon Mongkalig |
| Call Number | AIT Diss. no.ISE-05-02 |
| Subject(s) | Heuristic programming Production scheduling |
| Note | A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Engineering, School of Advanced Technologies |
| Publisher | Asian Institute of Technology |
| Series Statement | Dissertation ; no. ISE-05-02 |
| Abstract | This dissertation looks into new job shop scheduling problems with new measures of performance and new constraints. New heuristic methods, which are sequential NT-T-L heuristic approach and sequential NT-T-E&T heuristic method, are developed to solve job shop scheduling problems with earliness and tardiness penalties. The experimental results indicate that active schedules generated by the sequential NT-T-E&T heuristic method is significantly superior to the efficient bi-direction scheduling algorithm, and other heuristics. The performance measures proposed in this research are new customer-based measures of performance. The repetitive penalties increase at a constant progressive rate, depending on how many times late delivery of finished products to each customer occurs. The new performance measures are as follows: (i) total progressive weighted tardiness and (ii) total earliness and progressive weighted tardiness. New constraints, which are intermachine overlapping sequence-dependent setup times, are proposed in the new job shop scheduling problems. To reduce machine idle time and generate more effective complete schedules, direct processing times of preceding operations and machine setups of successive operations of the same job (batch of parts) are initiated simultaneously. New heuristic methods, which are the MPWT heuristic method, and five modified priority rules - LWKRS, MWKRS, SMST, SSPT, and SSTPT rules, are developed to solve conflicting operations in the set of active and nondelay schedules. There are three important experiments. The objective of the first experiment is to determine the necessity of sequence-dependent setup time consideration in the priority rules to solve the conflicting operations in the set of active and nondelay schedules. The experimental results indicate that, based on the following measures of performance: (i) total progressive weighted tardiness (ii) total earliness and progressive weighted tardiness and (iii) total earliness and tardiness, the modified priority rules with sequence-dependent setup time consideration are superior to the classical priority rules. The objective of the second experiment is to compare the active schedules generated by the MPWT heuristic method with the optimal solution. Based on total earliness and progressive weighted tardiness, it can be found that four out of ten results of the proposed heuristic procedure yield the optimal solution, and the percentage of the difference between the results of the proposed heuristic approach and the optimal solution are less than 20%. Therefore, the modified active schedule generation algorithm using the MPWT heuristic method yields very good results with significantly less computational time. The objective of the third experiment is to compare the proposed MPWT heuristic method with efficient heuristics, which are the BATCS, SMST, and LWKRS rules for solving the conflicting operations in the set of active schedules. The results obtained by the third experiment indicate that for solving the conflicting operations in the set of active schedules, the proposed MPWT heuristic method is superior to the BATCS, SMST, and LWKRS rules based on total earliness and progressive weighted tardiness, and total earliness and tardiness performance measures. An automotive parts factory is selected to be a case study. The MPWT heuristic method is then compared with other efficient heuristics based on the real scheduling data. The average of total earliness and progressive weighted tardiness of the schedules obtained by the modified active schedule generation algorithm using the MPWT heuristic method is lower than that of the modified active schedule generation algorithm using the sequential NT-T-E&T heuristic method and the BATCS rule, the modified nondelay schedule generation algorithm using the SSPT rule and the modified nondelay schedule generation algorithm using the EDD rule by 8.8%, 13.15%, 29.7%, and 30.95%, respectively. |
| Year | 2005 |
| Corresponding Series Added Entry | Asian Institute of Technology. Dissertation ; no. ISE-05-02 |
| Type | Dissertation |
| School | School of Advanced Technologies (SAT) |
| Department | Department of Industrial Systems Engineering (DISE) |
| Academic Program/FoS | Industrial Systems Engineering (ISE) |
| Chairperson(s) | Tabucanon, Mario T.; |
| Examination Committee(s) | Paul, H;Bohez, Erik L. J.;Nguyen Van Hop;Cheng, T. C. Edwin; |
| Scholarship Donor(s) | The Royal Thai Government;Dhurakij Pundit University, Thailand; |
| Degree | Thesis (Ph.D.) - Asian Institute of Technology, 2005 |