Fabrication scheduling on a single machine with due date constraints |
| |
Affiliation: | 1. Centre for Advanced Jet Engineering Technologies (CaJET), School of Mechanical Engineering, Shandong University, Jinan 250061, PR China;2. Key Laboratory of High Efficiency and Clean Mechanical Manufacture, Shandong University, Ministry of Education, PR China;3. National Demonstration Center for Experimental Mechanical Engineering Education (Shandong University), PR China;1. Key Laboratory of High-efficiency and Clean Mechanical Manufacture (Ministry of Education), National Demonstration Center for Experimental Mechanical Engineering Education (Shandong University), School of Mechanical Engineering, Shandong University, Jinan, 250061, PR China;2. University of Health and Rehabilitation Sciences, Qingdao, 266000, China;1. College of Chemistry and Chemical Engineering, Southwest Petroleum University, Chengdu City 610500, Sichuan Province, PRChina;2. State Key Lab of Oil and Gas Reservoir Geology and Exploitation, Southwest Petroleum University, Chengdu City 610500, Sichuan Province, PRChina |
| |
Abstract: | There is a fabrication machine available for processing a set of jobs. Each job is associated with a due date and consists of two parts, one is common among all products and the other is unique to itself. The unique components are processed individually and the common parts are grouped into batches for processing. A constant setup time is incurred when each batch is formed. The completion time of a job is defined as the time when both of its unique and common components are completed. In this paper, we consider two different objectives. The first problem seeks to minimize the maximum tardiness, and the second problem is to minimize the number of tardy jobs. To minimize the maximum tardiness, we propose a dynamic programming algorithm that optimally solves the problem in polynomial time. Next, we show NP-hardness proof and design a pseudo-polynomial time dynamic programming algorithm for the problem of minimizing the number of tardy jobs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|