Parallel machine earliness and tardiness scheduling with proportional weights |
| |
| Affiliation: | 1. State Key Laboratory of Digital Manufacturing Equipment & Technology in Huazhong University of Science & Technology, Wuhan, 430074, PR China;2. Grupo de Sistemas de Optimización Aplicada, Instituto Tecnológico de Informática, Ciudad Politécnica de la Innovación, Edifico 8G, Acc. B. Universitat Politècnica de València, Camino de Vera s/n, 46021, València, Spain;1. School of Industrial Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran;2. School of Industrial Engineering and Center of Excellence for Intelligence Based Experimental Mechanics, College of Engineering, University of Tehran, Tehran, Iran;3. LCFC, Arts et Métiers Paris Tech, Metz, France;4. Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran |
| |
| Abstract: | In this paper we study the problem of scheduling n jobs with a common due date and proportional early and tardy penalties on m identical parallel machines. We show that the problem is NP-hard and propose a dynamic programming algorithm to solve it. We also propose two heuristics to tackle the problem and analyze their worst-case error bounds.Scope and purposeScheduling problems to minimize the total weighted earliness and tardiness (WET) arise in Just-in-time manufacturing systems, where one of the objectives is to complete each job as close to its due date as possible. The earliness and tardiness weights of a job in WET tend to increase with the value of the job. Because processing time is often a good surrogate for the value of a job, it is reasonable to consider weights that are proportional to job processing times. In this paper we study the parallel identical machine WET problem with proportional weights. We propose both exact and approximation algorithms to tackle the problem. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
